POJ-2251 Dungeon Master

B - Dungeon Master (POJ - 2251)
POJ-2251 Dungeon Master

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 30+5;

char b[N][N][N] = {{{0}}};
bool vis[N][N][N] = {{{0}}};
int l, r, c, ans = 0;

int dx[] = { 1, -1,  0,  0,  0,  0};
int dy[] = { 0,  0,  1, -1,  0,  0};
int dz[] = { 0,  0,  0,  0,  1, -1};

struct P {
    int z, x, y;
    int step;
};
P sp;

bool bfs() {
    memset(vis, 0, sizeof(vis));

    sp.step = 0;

    queue<P> q;
    q.push(sp);
    vis[sp.z][sp.x][sp.y] = 1;

    while(!q.empty()) {
        P tp = q.front();
        q.pop();

        P np = tp;

        for(int i=0; i<6; i++) {
            int z = np.z = tp.z + dz[i];
            int x = np.x = tp.x + dx[i];
            int y = np.y = tp.y + dy[i];
            np.step = tp.step+1;

            if(z<0 || z>=l || x<0 || x>=r || y<0 || y>=c) {
                continue;
            }
            if(b[z][x][y]=='#') {
                continue;
            }
            if(b[z][x][y]=='E') {
                ans = np.step;
                return true;
            }
            if(b[z][x][y]=='.' && vis[z][x][y]==false) {
                vis[z][x][y] = true;
                q.push(np);
            }
        }
    }
    return false;
}

int main(void) {
    while(scanf("%d%d%d", &l, &r, &c)==3 && l && r && c) {
        ans = 0;

        for(int i=0; i<l; i++) {
            for(int j=0; j<r; j++) {
                for(int k=0; k<c; k++) {
                    scanf(" %c", &b[i][j][k]);
                    if(b[i][j][k]=='S') {
                        sp.z = i;
                        sp.x = j;
                        sp.y = k;
                    }
                }
            }
        }
        if(bfs())
            printf("Escaped in %d minute(s).\n", ans);
        else
            printf("Trapped!\n");
    }
    return 0;
}

上一篇:python脚本在ZMQ recv()中超时后未终止


下一篇:【POJ - 2251】Dungeon Master (bfs+优先队列)