Informatika gyűjtemény

Egy szinttel feljebb 15.cpp

2004050607080910

<<  10. óra  >>

<<  15-ös játék  >>

NézetNyomtat

15.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: 3 KB
/*
    Informatika: algoritmus szakkor
    Feladat: 15-os jatek
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/10ora/puzzle15
    Uray M. Janos, 2009. november 24.
*/
#include <stdio.h>

#define MaxDepth 10

// A tablat tarolo adatszerkezet
struct s15 {
    // A mezok erteke sorfolytonosan (0, ha ures)
    char Sq[16];
    // Az ures negyzet helye
    char Empty;
    
    // Az alapallas beallitasa
    void Init (void) {
        for (int I = 0; I < 16; I++)
            Sq[I] = (I + 1) % 16;
        Empty = 15;
    }
    // Mozgatas egy adott iranyba
    inline void MoveEmpty (int D) {
        Sq[Empty] = Sq[Empty + D];
        Sq[Empty + D] = 0;
        Empty += D;
    }
    void Print (void) {
        for (int I = 0; I < 16; I++)
            printf("%d ", Sq[I]);
        printf(": %d\n", Empty);
    }
} Step[MaxDepth], Sol;
// Step: allapotok a visszalepeses kereses soran
// Sol: a megoldas

// A lepes melysege
int Depth = 0;
// A kimeneti fajlba irando karakterlanc
char Moves[MaxDepth + 1] = {0};

bool operator == (const s15 &, const s15 &);

bool Read (const char *, s15 &);
bool Write (const char *, const char *);

bool Solvable (const s15 &);
bool Backtrack (void);

int main (int AN, char * Args []) {
    if (AN < 3)
        return 1;
    if (!Read(Args[1], Step[0]))
        return 1;
    Sol.Init();
    if (Backtrack())
        Write(Args[2], Moves);
    else
        Write(Args[2], "Nincs megoldas.");
    
    return 0;
}

bool operator == (const s15 & A, const s15 & B) {
    for (int I = 0; I < 16; I++)
        if (A.Sq[I] != B.Sq[I])
            return false;
    return true;
}

// Olvasas fajlbol
bool Read (const char * FN, s15 & In) {
    FILE * F = fopen(FN, "rt");
    int B;
    if (F == NULL)
        return false;
    for (int I = 0; I < 16; I++) {
        fscanf(F, "%d ", &B);
        In.Sq[I] = B;
        if (B == 0)
            In.Empty = I;
    }
    fclose(F);
    return true;
}
// Iras fajlba
bool Write (const char * FN, const char * Out) {
    FILE * F = fopen(FN, "wt");
    if (F == NULL)
        return false;
    fprintf(F, "%s\n", Out);
    fclose(F);
    return true;
}

// Egy adott allapot elvileg megoldhato-e
bool Solvable (const s15 & S) {
    int I, J, X = 0;
    // Inverzioszam
    for (I = 0; I < 16; I++)
        for (J = I + 1; J < 16; J++)
            if (S.Sq[I] > S.Sq[J])
                X++;
    return (X + (3 - S.Empty % 4) + (3 - S.Empty / 4)) % 2 == 0;
}

// A visszalepeses kereses fuggvenye (parameterek helyett globalis valtozokat hasznal)
bool Backtrack (void) {
    // Az egyes iranyokra jellemzo elmozdulas
    static char Dir[4] = {1, -4, -1, 4};
    // Az egyes iranyokat jelolo betuk
    static char Let[4] = {'J', 'F', 'B', 'L'};
    // Az egyes iranyok ellentetet jelolo betuk (az elozo lepessel valo osszehasonlitas miatt)
    static char RLet[4] = {'B', 'L', 'J', 'F'};
    
    // Ha megoldottuk, akkor vege a keresesnek, mert csak egy megoldas kell
    if (Step[Depth] == Sol) {
        // Stringet lezaro nulla karakter
        Moves[Depth] = 0;
        return true;
    }
    
    // Ha elertuk a keresesi melyseget, azaz ha nem talaltunk megoldast, akkor visszalepunk
    if (Depth + 1 == MaxDepth)
        return false;
    
    int I, J;
    char PrevLet = Depth > 0 ? Moves[Depth - 1] : ' ';
    
    // Tovabblepes
    Step[Depth + 1] = Step[Depth];
    Depth++;
    
    // A negy irany kiprobalasa
    for (I = 0; I < 4; I++) {
        // Ha az elozo lepes ezzel ellentetes iranyban tortent, akkor nem lepunk erre
        if (RLet[I] == PrevLet)
            continue;
        // Ha az irany kivul esne a tablan, akkor sem lepunk erre
        if (Step[Depth].Empty + Dir[I] < 0 || Step[Depth].Empty + Dir[I] >= 16)
            continue;
        // Elorelepes
        Step[Depth].MoveEmpty(Dir[I]);
        Moves[Depth - 1] = Let[I];
        // Az elert allapot volt-e mar
        for (J = 0; J < Depth; J++)
            if (Step[J] == Step[Depth])
                break;
        // Ha meg nem volt, akkor a backtrack folytatasa
        if (J == Depth && Backtrack())
            return true;
        // Visszalepes
        Step[Depth].MoveEmpty(-Dir[I]);
    }
    Depth--;
    return false;
}
(Vissza)