2157:Maze

keyword

迷路　DFS　C++

概要

2次元平面でドア、鍵付きの迷路が与えられる(20*20以下)。クリアできるかどうかを判定する問題。
ドアを開ける度に行動範囲が広がるのでドアを開ける度に探索をやり直す。効率は悪いけどサイズが小さいので余裕を持ってAC。

char board[21][21];
int keys[5];
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
int n, m;
bool isOk;

void dfs(int y, int x){
    if(isOk) return ;
    char c = board[y][x];
    if(c == 'G'){
        isOk = true;
        return ;
    }
    else if('a' <= c && c <= 'e'){
        board[y][x] = '*';
        keys[c-'a']--;
    }
    else if('A' <= c && c <= 'E'){
        if(!keys[c-'A'])
            board[y][x] = '*';
        else return ;
    }
    else if(c == '.'){
        board[y][x] = '*';
    }
    for(int k=0; k<4; k++){
        int ny = y + dy[k], nx = x + dx[k];
        if(0<=ny && ny<n && 0<=nx && nx<m 
                && board[ny][nx]!='*' && board[ny][nx]!='X')
            dfs(ny,nx);
    }
    return ;
}


int main(){
    int i,j;
    int sy, sx;
    while(scanf("%d%d\n",&n,&m), n){
        REP(i,n){
            scanf("%s\n",board[i]);
        }
        REP(i,5) keys[i] = 0;
        isOk = false;


        REP(i,n){
            REP(j,m){
                char c = board[i][j];
                if(c == 'S'){
                    sy = i;
                    sx = j;
                    board[i][j] = '.';
                }
                else if('a' <= c && c <= 'e'){
                    keys[c-'a']++;
                }
            }
        }


        int cnt = 0;
        while(!isOk){
            dfs(sy,sx);
            int tmp = 0;
            REP(i,n)REP(j,m)if(board[i][j] == '*'){
                tmp++;
                board[i][j] = '.';
            }
            if(cnt >= tmp) break;
            cnt = tmp;
        }

        if(isOk) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}