一、题目大意
迷宫中有墙(X),门(A\B\C\D\E),路(.)，钥匙(a\b\c\d\e), 起点(S), 终点(G)几大元素，如果出现了门，对应的钥匙至少有一把，必须要搜集到所有的钥匙才能够通过门。问从起点能否到达终点?

二、解题思路
(WA): 默认为对4个方向不分先后的直接DFS，期间保留现有的钥匙。无法解决以下情况(如果搜索方向先向正下方)。

Sa
AB
GB
output:No

(AC): 每一次DFS都执行找钥匙的使命，在找钥匙的过程中:

• (1)如果到达了终点，则能够到达，结束所有过程。
• (2)如果遇到可以通过的门，则一定能通过该门，直接把该门删去，变为.。
• (3)执行每次找钥匙的目的是为了在能到达的区域中找到尽可能多的钥匙。
• (4)若一次找钥匙行动找到的钥匙能够删除一道门，则删除该门，继续找钥匙。
• (5)一直重复直到一次找钥匙行动没有办法删掉一道门。若还没到达终点，则终点不可达。

代码

#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;

const int MAX = 25;
int visited[MAX][MAX];
char grad[MAX][MAX];
int flag;
int key2num[200];
int need_num[200];
int n, m;
int sx, sy;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x, int y)
{
    //cout << x << " " << y << endl;
    for(int i=0; i<4; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        if(nx < 0 || nx >= n || ny < 0 || ny >=m)
            continue;
        if(grad[nx][ny] == 'X')
            continue;
        if(visited[nx][ny])
            continue;
        if(grad[nx][ny] == '.')
        {
            visited[nx][ny] = 1;
            dfs(nx, ny);
        }
        if(grad[nx][ny] >= 'a' && grad[nx][ny] <= 'e')
        {
            visited[nx][ny] = 1;
            key2num[grad[nx][ny]]++;
            dfs(nx, ny);
        }
        if(grad[nx][ny] >= 'A' && grad[nx][ny] <='E')
        {
            if(key2num[grad[nx][ny] + ('a'-'A')] == need_num[grad[nx][ny] + ('a'-'A')])
            {
                visited[nx][ny] = 1;
                grad[nx][ny] = '.';
                dfs(nx, ny);
            }
        }
        if(grad[nx][ny] == 'G')
        {
            flag = 1;
            return;
        }

        if(flag)
            return;
    }
}
int main()
{
   while(cin >> n >> m)
   {
       if(n == 0 && m == 0)
            break;
       memset(visited, 0, sizeof(visited));
       memset(key2num, 0, sizeof(key2num));
       memset(need_num, 0, sizeof(need_num));
       for(int i=0; i<n; i++)
       {
           for(int j=0; j<m; j++)
           {
               cin >> grad[i][j];
               if(grad[i][j] == 'S')
               {
                   sx = i;
                   sy = j;
               }
               if(grad[i][j] >= 'a' && grad[i][j] <= 'e')
                    need_num[grad[i][j]]++;
           }
       }
       flag = 0;
       visited[sx][sy] = 1;
       dfs(sx, sy);
       while(true)
       {
            if(flag)
                break;
            int delete_door=0;
            for(int i=0; i<n; i++)
            {
                for(int j=0; j<m; j++)
                {
                    if(grad[i][j] >= 'A' && grad[i][j] <='E' && (need_num[grad[i][j]+'a'-'A'] == key2num[grad[i][j]+'a'-'A']))
                    {
                        delete_door=1;
                        grad[i][j] = '.';
                        break;
                    }
                }
                if(delete_door)
                    break;
            }
            if(!delete_door)
                 break;
            visited[sx][sy] = 1;
            memset(visited, 0, sizeof(visited));
            memset(key2num, 0, sizeof(key2num));
            dfs(sx, sy);
       }
       if(flag)
            printf("YES\n");
       else
            printf("NO\n");
   }
   return 0;
}