Informatika gyűjtemény

Egy szinttel feljebb exactcover.cpp

2004050607080910

<<  8. óra  >>

<<  Kömal fórum feladat  >>

NézetNyomtat

exactcover.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: 2 KB
/*
    Informatika: algoritmus szakkor
    Feladat: Pontos fedes
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/07ora/komal
    Uray M. Janos, 2009. november 3.
*/
#include <stdio.h>

#define MaxWalls 5
#define MaxPieces 336
#define FullInt64 0xFFFFFFFFFFFFFFFFLLU
#define ZeroInt64 0x0000000000000000LLU

typedef unsigned long long int int64;
typedef unsigned long int dword;
typedef unsigned char byte;

// Az alakzatok adatai minden lehetseges allasban (64 bites bitmezo), es egy logikai valtozo, hogy az adott falak mellett melyik mukodik
struct sPiece {
    int64 Loc;
    bool bIn;
} Piece[MaxPieces];
// A falak adatai (64 bites bitmezo, azon ket mezore, amely kozott van a fal)
int64 Wall[MaxWalls] = {
    
};
int PieceNum = 0, SolNum = 0;

// Az alakzatok a nyolc lehetseges iranyban
byte P23[4][4] = {{0, 1, 8, 16}, {0, 1, 9, 17}, {0, 8, 16, 17}, {1, 9, 16, 17}};
byte P32[4][4] = {{0, 1, 2, 8}, {0, 1, 2, 10}, {0, 8, 9, 10}, {2, 8, 9, 10}};

void GeneratePieces (void);
int Backtrack (int64, int);
void PrintInt64 (int64);
void PrintSolution (void);

int main (void) {
    GeneratePieces();
    printf("%d\n", Backtrack(0, 0));
    return 0;
}

// Az alakzatok osszes lehetseges allasanak eloallitasa
void GeneratePieces (void) {
    int64 BF;
    int I, J, K;
    for (I = 0; I < 4; I++) {
        BF = 0;
        for (J = 0; J < 4; J++)
            BF |= 1 << P23[I][J];
        for (J = 0; J < 6; J++)
            for (K = 0; K < 7; K++)
                Piece[PieceNum++].Loc = BF << (J * 8 + K);
        
        BF = 0;
        for (J = 0; J < 4; J++)
            BF |= 1 << P32[I][J];
        for (J = 0; J < 7; J++)
            for (K = 0; K < 6; K++)
                Piece[PieceNum++].Loc = BF << (J * 8 + K);
    }
    for (int I = 0; I < PieceNum; I++)
        Piece[I].bIn = false;
}

// A backtrack fuggveny.
// Cov: a mar lefedett mezok bitmezoben
// X: a kovetkezo probalhato alakzat indexe
// Visszateresi ertek: a lehetseges lefedesek szama az adott allapotbol kiindulva
int Backtrack (int64 Cov, int X) {
    // Ha a lefedes mar teljes, akkor talalt egy lehetseges lefedest
    if (Cov == FullInt64) {
        PrintSolution();
        return 1;
    }
    
    int Q = 0;
    // X-tol kezdve keres beillesztheto alakzatokat, es azzal folytatja a backtracket.
    for (int I = X; I < PieceNum; I++)
        if ((Piece[I].Loc & Cov) == ZeroInt64) {
            Piece[I].bIn = true;
            Q += Backtrack(Cov | Piece[I].Loc, I + 1);
            Piece[I].bIn = false;
        }
    // A meghivott backtrackek eredmenyenek osszeget adja vissza.
    return Q;
}

void PrintInt64 (int64 A) {
    printf("%08lX%08lX", *((dword *)&A + 1), *(dword *)&A);
}
void PrintSolution (void) {
    int64 Mask = 1;
    int I, J, K;
    for (I = 0; I < 64; I++) {
        K = 0;
        for (J = 0; J < PieceNum; J++)
            if (Piece[J].bIn) {
                if ((Piece[J].Loc & Mask) != ZeroInt64)
                    printf("%2d ", K);
                K++;
            }
            
        if (I % 8 == 7)
            printf("\n");
        Mask <<= 1;
    }
    printf("\n");
}
(Vissza)