3083:Children of the Candy Corn

keyword

探索　C++

概要

2次元の迷路が与えられる。右手則、左手則でゴールにたどり着くまでの時間と最短の時間を求める問題。
愚直に書くだけ。右手則でゴールにたどり着けることは保証してよいらしい。

char board[45][45];
int dist[45][45];
int w, h, Left, Right, shortest;
int sx, sy;
int dx[] = {1,0,-1,0}, dy[] = {0,-1,0,1};

inline void goRight(int y, int x, int dir){
    if(board[y][x] == 'E') return;
    for(int k=0; k<4; k++){
        int rd = (dir+3+k)&3;
        int ny = y + dy[rd],
            nx = x + dx[rd];
        if(board[ny][nx] != '#'){
            goRight(ny,nx,rd);
            Right++;
            return ;
        }
    }
}

inline void goLeft(int y, int x, int dir){
    if(board[y][x] == 'E') return;
    for(int k=0; k<4; k++){
        int rd = (dir+5-k)&3;
        int ny = y + dy[rd],
            nx = x + dx[rd];
        if(board[ny][nx] != '#'){
            Left++;
            goLeft(ny,nx,rd);
            return ;
        }
    }
}

inline int bfs(){
    queue< pair<pair<int,int>,int> > Q;
    int i, j, k;
    REP(i,h+2)REP(j,w+2) dist[i][j] = 1<<10;
    Q.push( MP(MP(sy,sx),1) );
    dist[sy][sx] = 1;
    while(!Q.empty()){
        int y = Q.front().first.first,
            x = Q.front().first.second,
            d = Q.front().second;
        Q.pop();
        REP(k,4){
            int ny = y + dy[k],
                nx = x + dx[k];
            if(dist[ny][nx] == 1<<10 && board[ny][nx] != '#'){
                dist[ny][nx] = d+1;
                if(board[ny][nx] == 'E') return d+1;
                Q.push( MP(MP(ny,nx), d+1) );
            }
        }
    }
    return 0;
}

int main(){
    int rept;
    scanf("%d\n",&rept);
    while(rept--){
        int i, j, dir;
        Right = Left = 1;
        scanf("%d%d\n",&w,&h);
        REP(i,h+2)REP(j,w+2) board[i][j] = '#';
        FOR(i,1,h+1){
            FOR(j,1,w+1){
                board[i][j] = getchar();
                if(board[i][j] == 'S'){
                    sy = i;
                    sx = j;
                    if(i==1) dir = 3;
                    if(i==h) dir = 1;
                    if(j==1) dir = 0;
                    if(j==w) dir = 2;
                }
            }
            scanf("\n");
        }
        goLeft(sy,sx,dir);
        goRight(sy,sx,dir);
        shortest = bfs();
        printf("%d %d %d\n",Left,Right,shortest);
    }
    return 0;
}