Maximum Winter-Contest 2011 G: Stacked Rotatable Mazes

keyword

幅優先探索　C++

問題概要

3次元の迷路の最短距離を求める問題。ただし下方向への移動はできず、上方向には特定のマスからしかいけない。また、上に登る前に上の層を任意に回転させることができる。

解法

定石通り幅優先するだけ。サンプルが珍しく親切。

char board[4][MAX][MAX][MAX];
int N, M;
int dz[] = {1,0,0,0,0};
int dy[] = {0,1,-1,0,0};
int dx[] = {0,0,0,1,-1};

bool isIn(int z, int y, int x){
    return 0<=z && z<M && 0<=y && y<N && 0<=x && x<N;
}

void init(){
for(int k=1; k<4; k++){
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            for(int jj=0; jj<N; jj++){
                board[k][i][j][jj] = board[k-1][i][jj][N-1-j];
            }
        }
    }
}
}

struct position{
    int k, z, y, x, d;
};

int solve(){
    init();
    int sx,sy;
    for(int i=0; i<N; i++)for(int j=0; j<N; j++)if(board[0][0][i][j]=='S'){
        sx = j; sy = i;
    }
    board[0][0][sy][sx] = '*';
    queue<position> Q;
    Q.push((position){0,0,sy,sx,0});
    while(!Q.empty()){
        position tp = Q.front(); Q.pop();
        for(int k=0; k<5; k++){
            int nz = tp.z + dz[k], ny = tp.y + dy[k], nx = tp.x + dx[k];
            if(!isIn(nz,ny,nx)) continue;
            if(!k){
                if(board[tp.k][tp.z][tp.y][tp.x] == 'Z')for(int kk=0; kk<4; kk++){
                    if(board[(tp.k+kk)%4][nz][ny][nx] == 'G') return tp.d+1;
                    if(board[(tp.k+kk)%4][nz][ny][nx] == '.'){
                        Q.push((position){(tp.k+kk)%4,nz,ny,nx,tp.d+1});
                        board[(tp.k+kk)%4][nz][ny][nx] = '*';
                    }
                }
            }
            else{
                if(board[tp.k][nz][ny][nx] != '*' && board[tp.k][nz][ny][nx] != 'Z'){
                    if(board[tp.k][nz][ny][nx] == 'G') return tp.d+1;
                    Q.push((position){tp.k,nz,ny,nx,tp.d+1});
                    board[tp.k][nz][ny][nx] = board[tp.k][nz][ny][nx]=='U'?'Z':'*';
                }
            }
        }
    }
    return -1;
}

int main(){
    while(scanf("%d%d ",&N,&M)){
        if(!N && !M) break;
        for(int i=0; i<M; i++){
            for(int j=0; j<N; j++){
                scanf("%s ",board[0][i][j]);
            }
        }
        printf("%d\n",solve());
    }
    return 0;
}