<dl class="problem&#45;display" style="font&#45;size&#58;14px&#59;color&#58;rgb&#40;70&#44;70&#44;70&#41;&#59;font&#45;family&#58;Tahoma&#44; Arial&#44; sans&#45;serif&#44; simsun&#59;"> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 描述 </dt> <dd>

一个叫ACM的寻宝者找到了一个藏宝图,它根据藏宝图找到了一个迷宫,这是一个很特别的迷宫,迷宫里有N个编过号的门(N<=5),它们分别被编号为A,B,C,D,E.为了找到宝藏,ACM必须打开门,但是,开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙(每个门都至少有一把钥匙),例如:现在A门有三把钥匙,ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM,他能不能顺利的得到宝藏。

 

<dl class="others"> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 输入 </dt> <dd> 输入可能会有多组测试数据(不超过10组)。
每组测试数据的第一行包含了两个整数M,N(1<N,M<20),分别代表了迷宫的行和列。接下来的M每行有N个字符,描述了迷宫的布局。其中每个字符的含义如下:
.表示可以走的路
S:表示ACM的出发点
G表示宝藏的位置
X表示这里有墙,ACM无法进入或者穿过。
A,B,C,D,E表示这里是门,a,b,c,d,e表示对应大写字母的门上的钥匙。
注意ACM只能在迷宫里向上下左右四个方向移动。

最后,输入0 0表示输入结束。 </dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 输出 </dt> <dd> 每行输出一个YES表示ACM能找到宝藏,输出NO表示ACM找不到宝藏。 </dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 样例输入 </dt> <dd>
4 4 
S.X. 
a.X. 
..XG 
.... 
3 4 
S.Xa 
.aXB 
b.AG 
0 0
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 样例输出 </dt> <dd>
YES 
NO
</dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 来源 </dt> <dd> POJ月赛改编 </dd> <dt style="color&#58;rgb&#40;113&#44;32&#44;21&#41;&#59;font&#45;size&#58;16px&#59;font&#45;weight&#58;bold&#59;"> 上传者 </dt> <dd> 张云聪 </dd> </dl> </dd> </dl>

其实就是一道搜索题 卡了我一天多   不过还是挺喜欢这道题的 

其实广搜 深搜都能做 。在这里我是用深搜做的

主要就是判断遇到门的时候怎么办 。如果遇到门 1.当前的钥匙不足以开门 2.当前的钥匙可以开门

第二种就不用说了 。主要说说第一种情况 。如果当前的钥匙不足以开门 我们需要在地图其它的可行区域找全  是否能够找到剩余的钥匙 然后再回到门前

,对于如何回到门前呢?我们可以定义一个数组来存贮门的位置 当其它区域全部找全后我们再回到门前判断能不能开门即可

【AC代码】

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
char maze[25][25];
bool vis[25][25];
bool result;
int n,m;
int key[5],cur_key[5];
struct node{
   int x,y,exit;
}door[5];
void dfs(int x,int y)
{
    if(x<0||y<0||x>=n||y>=m||maze[x][y]=='X'||vis[x][y]==true) return;
    if(maze[x][y]>='A'&&maze[x][y]<='E'&&cur_key[maze[x][y]-'A']<key[maze[x][y]-'A'])
    {
        door[maze[x][y]-'A'].x=x,door[maze[x][y]-'A'].y=y,door[maze[x][y]-'A'].exit=1;
        return ;
    }
    vis[x][y]=true;
    if(maze[x][y]>='a'&&maze[x][y]<='e') cur_key[maze[x][y]-'a']++;
    if(maze[x][y]=='G'){
        result = true;
        return ;
    }
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y+1);
    dfs(x,y-1);
    //地图找完后回到门前再次判断是否可以开门
    for(int i=0; i<5; i++)
    {
        if(door[i].exit==true)
        {
            if(cur_key[i]==key[i])
            {
                int x = door[i].x;
                int y = door[i].y;
                dfs(x,y+1);
                dfs(x,y-1);
                dfs(x-1,y);
                dfs(x+1,y);
            }
        }
    }
}

int main()
{
    int st_x,st_y;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)return 0;
        memset(key,0,sizeof(key));
        memset(cur_key,0,sizeof(cur_key));
        memset(maze,0,sizeof(maze));
        memset(door,0,sizeof(door));
        memset(vis,0,sizeof(vis));
        char op;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                scanf(" %c",&op);
                maze[i][j] = op;
                if(op>='a'&&op<='a')
                {
                    key[op-'a']++;
                }
                if(op=='S')
                {
                    st_x = i,st_y = j;
                }
            }
        }
        result = false;
        dfs(st_x,st_y);
        if(result==true) puts("YES");
        else             puts("NO");
    }
    return 0;
}