zju2279 -- in the mirror.cpp

Zhejiang University Online Judge 第2277题至第2283题的代码和解题报告

// PROB         Zju Online Judge 2279 -- In the Mirror
// Algorithm    BFS
// Complexity   O(10*10*2^10)
// Author       LoveShsean
#include <stdio.h>
#include <string.h>

#define maxn 12
#define qSize 102410
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int p[11] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};

struct Tbat{
    int x, y, d;
} bat[101];
struct Tmirror{
    int x, y;
    bool left;
} mir[maxn];
int n, m, map[maxn][maxn], sx, sy, ox, oy, nBats, nMirrors;
bool f[1024][maxn][maxn], ok[1024][maxn][maxn];
int x[qSize], y[qSize], z[qSize], w[qSize];

// This function returns the sight direction through the mirror
int reflect(int sMirror, int sDir){
    if (!sMirror) return 3 - sDir;
    else {
        if (sDir < 2) return 1 - sDir;
        else return 5 - sDir;
    }
}

int solve(){
    // Get the Map for all the state of mirrors
    memset(ok, 0, sizeof(ok));
    for (int k = 0; k < p[nMirrors]; k++){
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                ok[k][i][j] = map[i][j] < 0 ? 0 : map[i][j];
        for (int i = 0; i < nBats; i++){
            int tx = bat[i].x, ty = bat[i].y, td = bat[i].d;
            while (map[tx][ty] != 0) {
                ok[k][tx][ty] = 0;
                if (map[tx][ty] < 0) td = reflect((k >> (-1 - map[tx][ty]) & 1), td);
                tx += dx[td];ty += dy[td];
            }
        }
    }
    // Init the Start State
    memset(f, 0, sizeof(f));
    int start(0);
    for (int i = 0; i < nMirrors; i++) start += p[i] * mir[i].left;
    // Breadth First Search
    int front = -1, rear = 0;
    x[0] = sx;y[0] = sy;z[0] = 0;w[0] = start;
    while (++front <= rear){
        // Go in 4 directions
        for (int i = 0; i < 4; i++){
            int tx = x[front] + dx[i], ty = y[front] + dy[i];
            if (!ok[w[front]][tx][ty]) continue;
            if (f[w[front]][tx][ty]) continue;
            f[w[front]][tx][ty] = 1;
            x[++rear] = tx;
            y[rear] = ty;
            z[rear] = z[front] + 1;
            w[rear] = w[front];
            if (tx == ox && ty == oy) return z[rear];
        }
        // Rorate the Mirrors
        for (int i = 0; i < nMirrors; i++){
            // ^ means xor in pascal
            int tw = w[front] ^ p[i];
            if (!ok[tw][x[front]][y[front]]) continue;
            if (f[tw][x[front]][y[front]]) continue;
            f[tw][x[front]][y[front]] = 1;
            x[++rear] = x[front];
            y[rear] = y[front];
            z[rear] = z[front] + 1;
            w[rear] = tw;
        }
    }
    return -1;
}
int main(int argc, char* argv[])
{
    while (scanf("%d %d", &n, &m) != EOF){
        //Read data
        nBats = nMirrors = 0;
        memset(map, 0, sizeof(map));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++){
                char c;
                while (scanf("%c", &c),
                c != 'S' && c != 'v' && c != 'E' && c != '/' &&
                c != '\\' && c != '#' && c != '^' && c != '.' &&
                c != '>' && c != '<');
                if (c == 'S') { sx = i; sy = j;map[i][j] = 1; }
                if (c == 'E') { ox = i; oy = j;map[i][j] = 1; }
                if (c == '.') map[i][j] = 1;
                if (c == '#') map[i][j] = 0;
                if (c == '^') {bat[nBats].x = i;bat[nBats].y = j;bat[nBats++].d = 0;map[i][j] = 1;}
                if (c == '>') {bat[nBats].x = i;bat[nBats].y = j;bat[nBats++].d = 1;map[i][j] = 1;}
                if (c == 'v') {bat[nBats].x = i;bat[nBats].y = j;bat[nBats++].d = 2;map[i][j] = 1;}
                if (c == '<') {bat[nBats].x = i;bat[nBats].y = j;bat[nBats++].d = 3;map[i][j] = 1;}
                if (c == '/') {mir[nMirrors].x = i;mir[nMirrors].y = j;mir[nMirrors].left = 1;nMirrors++;map[i][j] = -nMirrors;}
                if (c == '\\'){mir[nMirrors].x = i;mir[nMirrors].y = j;mir[nMirrors].left = 0;nMirrors++;map[i][j] = -nMirrors;}
            }
        //Solve it
        int ans = solve();
        if (ans < 0) printf("poor\n");
        else printf("%d\n", ans);
    }
    return 0;
}