POJ2157Maze[DFS !]

//
//  main.cpp
//  poj2157
//
//  Created by Candy on 10/1/16.
//  Copyright © 2016 Candy. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;
const int N=21,V=1e6+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x;
}
int n,m,sx,sy,flag=0;
char a[N][N];
struct doors{
    int k,x,y;
}door[N*N];
int cnt=0;
int vis[N][N],g[N][N],dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
struct keys{
    int has,tot;
}key[N];
int mark[N][N];
void dfs(int x,int y){//printf("dfs %d %d\n",x,y);
    vis[x][y]=1;
    if(a[x][y]==‘G‘){flag=1;return;}
    if(flag) return;
    for(int i=0;i<4;i++){
        int nx=x+dx[i],ny=y+dy[i];
        if(vis[nx][ny]) continue;
        if(nx<1||nx>n||ny<1||ny>m) continue;
        if(g[nx][ny]<=5&&g[nx][ny]>=1){
            int num=g[nx][ny];
            mark[nx][ny]=1;
            if(key[num].has<key[num].tot||(!key[num].tot)) continue;
        }
        if(g[nx][ny]>5) {
            int num=g[nx][ny]-5;
            key[num].has++;
            if(key[num].has==key[num].tot&&key[num].tot){//no key cannot in
                for(int j=1;j<=cnt;j++)
                    if(door[j].k==num&&mark[door[j].x][door[j].y]){
                        dfs(door[j].x,door[j].y);
                    }
            }
        }
        dfs(nx,ny);
    }
    //printf("end %d %d\n",x,y);
}
int main(int argc, const char * argv[]) {
    while(scanf("%d%d",&n,&m)&&n){
        memset(g,0,sizeof(g));
        memset(vis,0,sizeof(vis));
        memset(door,0,sizeof(door));
        memset(key,0,sizeof(key));
        memset(mark,0,sizeof(mark));
        cnt=0;
        for(int i=1;i<=n;i++){
            flag=0;
            scanf("%s",a[i]+1);
            for(int j=1;j<=m;j++){
                if(a[i][j]==‘S‘) sx=i,sy=j;
                else if(a[i][j]==‘X‘) vis[i][j]=1;
                else if(a[i][j]>=‘A‘&&a[i][j]<=‘E‘){
                    g[i][j]=a[i][j]-‘A‘+1;//1...5
                    door[++cnt].x=i;door[cnt].y=j;door[cnt].k=g[i][j];
                }else if(a[i][j]>=‘a‘&&a[i][j]<=‘e‘){
                    key[a[i][j]-‘a‘+1].tot++;
                    g[i][j]=a[i][j]-‘a‘+6;//6...10
                }
            }
        }
        dfs(sx,sy);
        if(flag) puts("YES");
        else puts("NO");
        //printf("%d %d %d",key[2].has,key[2].tot,door[2].k);
    }
    
    return 0;
}