nswoj 1178 - 迷宫寻宝（一）（深搜好题）
发布时间
阅读量：
阅读量
上题：
一个叫ACM的寻宝者找到了一个藏宝图，它根据藏宝图找到了一个迷宫，这是一个很特别的迷宫，迷宫里有N个编过号的门（N<=5)，它们分别被编号为A,B,C,D,E.为了找到宝藏，ACM必须打开门，但是，开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙（每个门都至少有一把钥匙），例如：现在A门有三把钥匙，ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM，他能不能顺利的得到宝藏。
输入 输入可能会有多组测试数据（不超过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表示输入结束。
输出 每行输出一个YES表示ACM能找到宝藏，输出NO表示ACM找不到宝藏。
样例输入
样例输出
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#define putt printf("$$$$$\n");
using namespace std;
int n,m,sx,sy,ex,ey;
char ch[25][25];
int vis[25][25];
int key[6],nowkey[6];
int dis[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
int x,y;
};
bool can_open(int x)//比较能否开门
{
// printf("key=%d nowkey\n",key[x],nowkey[x]);
if(key[x]==nowkey[x])
{
return 1;
}
return 0;
}
bool can_go(int x,int y)//能否走过去
{
if(x<0||y<0||x>=n||y>=m)
{
return 0;
}
if(ch[x][y]=='X')
{
return 0;
}
return 1;
}
int bfs()
{
queue<node>que;
node now,next;
now.x=sx;
now.y=sy;
while(!que.empty())
{
que.pop();
}
vis[sx][sy]=1;
que.push(now);
while(!que.empty())
{
now=que.front();
que.pop();
// printf("x=%d y=%d \n",now.x,now.y);
if(now.x==ex&&now.y==ey)//走到终点就直接跳出
{
return 1;
}
for(int i=0;i<4;i++)
{
next.x=now.x+dis[i][0];
next.y=now.y+dis[i][1];
if(can_go(next.x,next.y)&&!vis[next.x][next.y])//当符合条件的时候
{
if(ch[next.x][next.y]>='A'&&ch[next.x][next.y]<='E')//遇到门的时候
{
if(!can_open(ch[next.x][next.y]-'A'))
{
continue;
}
}
if(ch[next.x][next.y]>='a'&&ch[next.x][next.y]<='e')//遇到钥匙的时候 加一
{
nowkey[ch[next.x][next.y]-'a']++;
}
vis[next.x][next.y]=1;
ch[next.x][next.y]='.';//将所有的非X在此时都变成.
que.push(next);
}
}
}
return -1;
}
int main()
{
while(scanf("%d%d",&n,&m),m||n)
{
int flag=0;
memset(vis,0,sizeof(vis));
memset(ch,0,sizeof(ch));
memset(key,0,sizeof(key));
memset(nowkey,0,sizeof(nowkey));
for(int i=0;i<n;i++)
{
scanf("%s",ch[i]);
for(int j=0;j<m;j++)
{
if(ch[i][j]=='S')
{
sx=i;
sy=j;
}
else if(ch[i][j]=='G')
{
ex=i,ey=j;
}
else if(ch[i][j]=='.'||ch[i][j]=='X')
{
continue;
}
else if(ch[i][j]>='a'&&ch[i][j]<='e')
{
key[ch[i][j]-'a']++; //找到开这扇门的所需要的钥匙
}
}
}
// printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
/* for(int i=0;i<n;i++)
{
printf("%s\n",ch[i]);
}*/
// printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
for(int i=0;i<5;i++)//五次深搜
{
int t=bfs();
memset(vis,0,sizeof(vis));
/* for(int i=0;i<n;i++)
{
printf("%s\n",ch[i]);//由于是要改变地图的，所以每次深搜之后就把所改变的地图输出出来，这样比较容易找出哪里了错误了
被自己的机智所感动。
}*/
// printf("--------------------------\n");
if(t==1)
{
flag=1;
break;
}
}
if(flag)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
AI写代码AI写代码
全部评论 (0)
还没有任何评论哟~