2251:Dungeon Master

keyword

迷路　BFS　C++

概要

3次元の迷路を解いて最短経路の長さを求める問題。
2次元でやるのと同じようにBFSで探索する。pair >とか非常に面倒なのでintにまとめる。このテクニックに名前ってついているんだろうか。前は座標圧縮ってこれを指していると思っていたんだけど。

inline int toP(int x, int y, int z){
    return  (x<<16) + (y<<8) + z;
}

inline int getX(int p){
    return p>>16;
}

inline int getY(int p){
    return (p>>8)&255;
}

inline int getZ(int p){
    return p & 255;
}

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

int main(){
    int x, y, z, i, j, k, l, r, c, ed, ans;
    static int dist[34][34][34];
    static char map[34][34][34];
    char ch;

    while(scanf("%d%d%d\n",&l,&r,&c)){
        if(!(l||r||c))break;
        REP(i,34)REP(j,34)REP(k,34) dist[i][j][k] = -1;
        REP(i,34)REP(j,34)REP(k,34) map[i][j][k] = '#';
        queue<int> Q;

        REPONE(i,l){
            REPONE(j,r){
                REPONE(k,c){
                    scanf("%c", &ch);
                    map[i][j][k] = ch;
                    if(ch=='S'){
                        Q.push(toP(i,j,k));
                        dist[i][j][k] = 0;
                    }
                    if(ch=='E'){
                        ed = toP(i,j,k);
                    }
                }
                scanf("\n");
            }
            scanf("\n");
        }

        while(!Q.empty()){
            int p = Q.front(); Q.pop();
            REP(i,6){
                int nx = getX(p) + dx[i], ny = getY(p) + dy[i], nz = getZ(p) + dz[i];
                if(dist[nx][ny][nz] == -1 && map[nx][ny][nz] != '#'){
                    dist[nx][ny][nz] = dist[getX(p)][getY(p)][getZ(p)] + 1;
                    Q.push(toP(nx,ny,nz));
                }
            }
        }

        ans = dist[getX(ed)][getY(ed)][getZ(ed)];
        if(ans==-1) printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n", ans);
    }

    return 0;
}