Informatika gyűjtemény

uj_lab.cpp (Vissza)

Az alábbi letöltési lehetőségek közül választhatsz: (segítség)

	Karakterkódolás:
	Sortörés:

Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 9 KB

/*
    Informatika: algoritmus szakkor
    Feladat: at a labirintuson
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/14ora/atalabirintuson
    Uray M. Janos, 2010. januar 5.
*/
#include <stdio.h>

#define MaxSize 257
#define MaxLen 65025

typedef unsigned char byte;

class cRoute;
class cLab;

// Ut osztaly
class cRoute {
    private:
        // A bejart ut hossza
        int Len;
        // A bejart ut lepesei
        enum eStep {
            S_Forward,  // elore
            S_Left,     // balra
            S_Right     // jobbra
        } Step[MaxLen];

    public:
        void Init (void);
        int GetLen (void) {return Len;}

        void Push (eStep);
        void PushForward (void) {Push(S_Forward);}
        void PushLeft (void) {Push(S_Left);}
        void PushRight (void) {Push(S_Right);}

        eStep ChangeDirection (eStep);

        void Simplify (void);

        void MarkInLab (cLab &);

        void PrintToFile (FILE *);
};
// Labirintus osztaly
class cLab {
    private:
        // A labirintus merete (a kulso falakat is szamolva)
        int Size;
        // A labirintus elemeit tarolo ketdimenzios tomb
        enum eField {
            F_Space,        // ut
            F_Wall,         // fal
            F_Footprint,    // jart ut
        } Field[MaxSize][MaxSize];
        // Az ut
        cRoute Route;

    public:
        // Iranyok
        enum eDir {
            D_Right,    // jobbra
            D_Up,       // fel
            D_Left,     // balra
            D_Down      // le
        };

        void Run (const char *, const char *, const char *);

        bool Read (const char *);
        bool Write (const char *);

        static eDir DirTurnLeft (eDir);
        static eDir DirTurnRight (eDir);
        static eDir DirTurnBack (eDir);
        static void MoveDir (int &, int &, eDir);

        void SetField (int, int, eField);
        void SetFieldSpace (int X, int Y) {SetField(X, Y, F_Space);}
        void SetFieldWall (int X, int Y) {SetField(X, Y, F_Wall);}
        void SetFieldFootprint (int X, int Y) {SetField(X, Y, F_Footprint);}

        eField GetField (int, int);
        eField GetFieldDir (int, int, eDir);

        void Start (int &, int &, eDir &);
        bool Exit (int, int);

        void DeleteFootprints (void);

        void BuildLeftHandRoute (void);
        void BuildShortestRoute (void);
};

int main (int AN, char * Args []) {
    cLab Lab;
    if (AN < 4)
        return 1;
    Lab.Run(Args[1], Args[2], Args[3]);
    return 0;
}

// Az ut nullazasa
void cRoute::Init (void) {
    Len = 0;
}
// Az ut vegere ir egy adott lepest
void cRoute::Push (eStep S) {
    if (Len >= MaxLen)
        return;
    Step[Len++] = S;
}
// Lepes iranyanak megforditasa
cRoute::eStep cRoute::ChangeDirection (cRoute::eStep Step) {
    if (Step == S_Right)
        return S_Left;
    else if (Step == S_Left)
        return S_Right;
    else
        return Step;
}
// A zsakutcak levagasa
void cRoute::Simplify (void) {
    int I, J = 0, K, Right = 0;
    bool bChange;
    // A levagas ugy tortenik, hogy a Step[] tombot lemasolja onmagara ugy, hogy kihagyja a zsakutcakat. I jelenti a tomb forras-indexet, J pedig a cel-indexet a masolasnal.
    // Ha talal egy visszafordulast, akkor megnezi, hogy milyen mely a zsakutca, es annak megfeleloen allitja be az uj I es J ertekeket.
    for (I = 0; I < Len; I++) {
        // Egymast koveto jobbra fordulasok szamlalasa
        if (Step[I] == S_Right)
            Right++;
        else
            Right = 0;
        // Ha talalt ket jobbra fordulast egymas utan (azaz visszafordulast), akkor ott zsakutca van
        if (Right == 2) {
            bChange = true;
            // Zsakutca melysegenek meghatarozasa
            for (K = 1; true; K++) {
                // Step[I + K]: A visszafordulas utani K. lepes
                // Step[J - K - 1]: A visszafordulas elotti K. lepes (a -1 a kettos jobbra fordulas miatt van)
                // Ha ugy talalja, hogy a zsakutca veget ert, akkor kilep a ciklusbol
                if (Step[I + K] == S_Forward) {
                    if (Step[J - K - 1] != S_Forward)
                        break;
                } else {
                    if (Step[J - K - 1] == S_Forward)
                        break;
                    else if (Step[J - K - 1] == Step[I + K]) {
                        bChange = false;
                        K++;
                        break;
                    }
                }
            }
            // A 180 fokos iranyvaltozas miatt a zsakutcahoz kapcsolodo iranyok megforditasa
            if (bChange) {
                Step[I + K] = ChangeDirection(Step[I + K]);
                Step[J - K - 1] = ChangeDirection(Step[J - K - 1]);
            }
            // Zsakutca torlese
            I += K;
            J -= K;
        }
        Step[J++] = Step[I];
    }
    // Az ut hosszanak megvaltoztatasa
    Len -= I - J;
}
// Az ut jelolese egy adott labirintusban
void cRoute::MarkInLab (cLab & Lab) {
    int I, X, Y;
    cLab::eDir Dir;
    Lab.Start(X, Y, Dir);

    Lab.SetFieldFootprint(X, Y);
    for (I = 0; I < Len; I++)
        switch (Step[I]) {
            case S_Forward:
                Lab.MoveDir(X, Y, Dir);
                Lab.SetFieldFootprint(X, Y);
                break;
            case S_Left:
                Dir = Lab.DirTurnLeft(Dir);
                break;
            case S_Right:
                Dir = Lab.DirTurnRight(Dir);
                break;
        }
}
// Az ut kiirasa egy adott fajlba a megadott formatumban
void cRoute::PrintToFile (FILE * F) {
    int I, J;
    for (I = 0; I < Len; I++)
        switch (Step[I]) {
            case S_Forward: fprintf(F, "E"); break;
            case S_Left: fprintf(F, "B"); break;
            case S_Right: fprintf(F, "J"); break;
        }
    fprintf(F, "\n");
}

// A feladatok megoldasa
void cLab::Run (const char * In, const char * OutA, const char * OutB) {
    // Beolvasas
    Read(In);

    // A balkezes feladat megoldasa
    BuildLeftHandRoute();
    Route.MarkInLab(*this);
    Write(OutB);

    // A legrovidebb ut megtalalasa
    DeleteFootprints();
    BuildShortestRoute();
    Route.MarkInLab(*this);
    Write(OutA);
}
// A labirintus beolvasasa
bool cLab::Read (const char * FN) {
    FILE * F = fopen(FN, "r");
    if (F == NULL)
        return false;

    int I, J;
    char Str[MaxSize + 1];

    // Labirintus meretenek beolvasasa
    fscanf(F, "%d\n", &Size);
    if (Size > MaxSize) {
        fclose(F);
        return false;
    }
    // A kulso falakat is beleszamitjuk
    Size += 2;
    // Sorok olvasasa (az utolsot be sem olvassa, mert az mindig ugyanaz)
    for (I = 0; I < Size; I++) {
        // Sor beolvasasa stringkent
        fgets(Str, MaxSize + 1, F);
        // A sorok szetbontasa a 'Field' tombbe
        for (J = 0; J < Size; J++) {
            switch (Str[J]) {
                case ' ':
                    SetFieldSpace(J, I);
                    break;
                case '#':
                    SetFieldWall(J, I);
                    break;
            }
        }
    }
    fclose(F);
    return true;
}
// A feladat megoldasanak kiirasa
bool cLab::Write (const char * FN) {
    FILE * F = fopen(FN, "w");
    if (F == NULL)
        return false;

    int I, J;

    // Az uthossz kiirasa
    fprintf(F, "%d\n", Route.GetLen());
    // Az ut kiirasa
    Route.PrintToFile(F);

    // A labirintus kirajzolasa
    for (I = 0; I < Size; I++) {
        for (J = 0; J < Size; J++)
            switch (GetField(J, I)) {
                case F_Space: fputc(' ', F); break;
                case F_Wall: fputc('#', F); break;
                case F_Footprint: fputc('.', F); break;
            }
        fprintf(F, "\n");
    }
    fclose(F);
    return true;
}

// Irany balra forditasa
cLab::eDir cLab::DirTurnLeft (cLab::eDir Dir) {
    switch (Dir) {
        case D_Right: return D_Up;
        case D_Up: return D_Left;
        case D_Left: return D_Down;
        case D_Down: return D_Right;
    }
}
// Irany jobbra forditasa
cLab::eDir cLab::DirTurnRight (cLab::eDir Dir) {
    switch (Dir) {
        case D_Right: return D_Down;
        case D_Up: return D_Right;
        case D_Left: return D_Up;
        case D_Down: return D_Left;
    }
}
// Irany megforditasa
cLab::eDir cLab::DirTurnBack (cLab::eDir Dir) {
    switch (Dir) {
        case D_Right: return D_Left;
        case D_Up: return D_Down;
        case D_Left: return D_Right;
        case D_Down: return D_Up;
    }
}
// Egy koordinata mozgatasa adott iranyba
void cLab::MoveDir (int & X, int & Y, eDir Dir) {
    switch (Dir) {
        case D_Right: X++; return;
        case D_Up: Y--; return;
        case D_Left: X--; return;
        case D_Down: Y++; return;
    }
}

// Adott mezo beallitasa
inline void cLab::SetField (int X, int Y, cLab::eField F) {
    if (X >= 0 && X < Size && Y >= 0 && Y < Size)
        Field[Y][X] = F;
}
// A labirintus adott koordinataju mezojenek visszaadasa
inline cLab::eField cLab::GetField (int X, int Y) {
    return X >= 0 && X < Size && Y >= 0 && Y < Size ? Field[Y][X] : F_Wall;
}
// A labirintus adott mezojetol adott iranyban levo mezo visszaadasa
cLab::eField cLab::GetFieldDir (int X, int Y, eDir Dir) {
    MoveDir(X, Y, Dir);
    return GetField(X, Y);
}

// A kezdohely es irany beallitasa
inline void cLab::Start (int & X, int & Y, eDir & Dir) {
    X = 0;
    Y = 1;
    Dir = D_Right;
}
// Megnezi, hogy az adott hely a labirintus kijarata-e
inline bool cLab::Exit (int X, int Y) {
    return X == Size - 1 && Y == Size - 2;
}

// Utjelzes torlese
void cLab::DeleteFootprints (void) {
    int I, J;
    for (I = 0; I < Size; I++)
        for (J = 0; J < Size; J++)
            if (Field[I][J] == F_Footprint)
                Field[I][J] = F_Space;
}

// A balkezes feladat megoldasa
void cLab::BuildLeftHandRoute (void) {
    int X, Y;
    eDir Dir;

    Start(X, Y, Dir);

    // Ut nullazasa
    Route.Init();
    // Addig tart a ciklus, amig a kijarathoz nem ert (ez feltetelezi, hogy a feladatnak van megoldasa)
    while (!Exit(X, Y)) {
        // Az egyes iranyok vegignezese
        if (GetFieldDir(X, Y, DirTurnLeft(Dir)) != F_Wall) {
            // Balra lehet menni: balra fordulunk
            Dir = DirTurnLeft(Dir);
            Route.PushLeft();
        } else if (GetFieldDir(X, Y, Dir) != F_Wall) {
            // Elore lehet menni: nem fordulunk
        } else if (GetFieldDir(X, Y, DirTurnRight(Dir)) != F_Wall) {
            // Jobbra lehet menni: jobbra fordulunk
            Dir = DirTurnRight(Dir);
            Route.PushRight();
        } else {
            // Csak vissza lehet menni: ketszer jobbra fordulunk
            Dir = DirTurnBack(Dir);
            Route.PushRight();
            Route.PushRight();
        }
        // Elorelepunk az uj iranyba
        MoveDir(X, Y, Dir);
        Route.PushForward();
    }
}

void cLab::BuildShortestRoute (void) {
    Route.Simplify();
}

(Vissza)

A dokumentum tulajdonosa: Erben Péter; utolsó módosítás: 2010-01-17 21:20:51 (Erben Péter)
(C) 2004-2010 BDG programozás szakkör
Powered by BDG programozás szakkör & njcms v0.5.12