Informatika gyűjtemény

Egy szinttel feljebb ec2.cpp

2004050607080910

<<  8. óra  >>

<<  Kömal fórum feladat  >>

NézetNyomtat

ec2.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: Pontos fedes
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/07ora/komal
    Uray M. Janos, 2009. november 3.
*/
#include <stdio.h>
#include <time.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 es a mar kitoltott tablaresz mellett melyik rakhato le
struct sPiece {
    int64 Loc;
    bool bGood;
} Piece[MaxPieces];
// A falak adatai (64 bites bitmezo, azon ket mezore, amely kozott van a fal)
int64 Wall[MaxWalls] = {
    0x0000000000000003LLU,
    0x0000000000008080LLU,
    0x0000000000030000LLU,
    0x0000000000060000LLU,
    0x0000002020000000LLU
};
int PieceNum = 0, WallNum = 5, 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);
void CheckPieces (void);
int Backtrack (int64, int64);
void PrintInt64 (int64);
void PrintSolution (void);

int main (void) {
    clock_t C0;
    int Num;
    
    GeneratePieces();
    CheckPieces();
    C0 = clock();
    Num = Backtrack(0, 1);
    C0 = clock() - C0;
    printf("Solutions: %d\n", Num);
    printf("Time: %.2f s\n", C0 / (1.0 * CLOCKS_PER_SEC));
    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);
    }
}

// Minden egyes alakzatrol eldonti, hogy az adott falak mellett elfer-e.
void CheckPieces (void) {
    int I, J;
    for (I = 0; I < PieceNum; I++) {
        Piece[I].bGood = true;
        for (J = 0; J < WallNum; J++)
            if ((Piece[I].Loc & Wall[J]) == Wall[J])
                Piece[I].bGood = false;
    }
}

// A backtrack fuggveny.
// Cov: a mar lefedett mezok bitmezoben
// FE: a Cov-ban az elso ures mezo helyierteke (First Empty)
// Visszateresi ertek: a lehetseges lefedesek szama az adott allapotbol kiindulva
int Backtrack (int64 Cov, int64 FE) {
    // Ha a lefedes mar teljes, akkor talalt egy lehetseges lefedest
    if (Cov == FullInt64)
        return 1;
    // FE beallitasa az uj ertekre
    while ((Cov & FE) != ZeroInt64)
        FE <<= 1;
    
    int I, Q = 0;
    // Keres beillesztheto alakzatokat, amelyek az elso (FE-vel jelolt) mezot lefedik
    for (I = 0; I < PieceNum; I++)
        if (Piece[I].bGood && (Piece[I].Loc & FE) != ZeroInt64 && (Piece[I].Loc & Cov) == ZeroInt64) {
            Piece[I].bGood = false;
            Q += Backtrack(Cov | Piece[I].Loc, FE);
            Piece[I].bGood = true;
        }
    // 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)