nyoj82迷宫寻宝（一）
发布时间
阅读量：
阅读量
迷宫寻宝（一）
时间限制：1000 ms | 内存限制：65535 KB
难度：4
描述
一位名为ACM的寻宝者发现了藏宝图，并通过藏宝图的指引进入了这个迷宫。这个迷宫具有独特的性质，其中共有N扇编号分别为A、B、C、D、E（其中N≤5）的门。为了获取宝藏，寻宝者ACM需要打开这些门。然而，在开启每扇门前必须确保已经收集到了所有对应所需的钥匙（每个门都至少有一把钥匙）。例如：现在A号门前共有三把钥匙，则寻宝者必须收集齐这三把钥匙才能打开该扇门前的大门。请设计一个程序来判断寻宝者是否能够顺利获得宝藏。
测试数据的数量有限制（不超过10组）。
每组测试数据的第一行给出两个整数M和N（其中1 < M, N < 20），它们分别表示迷宫的行数和列数。
以下将详细描述迷宫的具体布局：
.标识通路的位置
S标记ACM团队的起始位置
G代表宝藏藏匿的具体地点
X则表明此处设有墙壁阻挡
A、B、C、D、E等字母代表门的具体位置
a,b,c,d,e则是相应的大写字母对应的钥匙编号
特别说明的是，在迷宫内部只有上下左右四个方向可供移动选择。
最后，输入0 0表示输入结束。
输出
每行输出一个YES表示ACM能找到宝藏，输出NO表示ACM找不到宝藏。
样例输入
4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0
样例输出
YES
NO
来源
POJ月赛改编
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
//地图
char map[25][25];
//遍历标记
bool vis[25][25];
//是否找到宝藏
bool result;
//钥匙总数
int key[5];
//当前找到的钥匙总数
int curKey[5];
int n,m;
int st_x,st_y;
struct node
{
int x,y;
bool exit;
}door[5];
void check();
void dfs(int x,int y)
{
if(x<0||y<0||x>=m||y>=n||map[x][y]=='X'||vis[x][y])
return ;
//遇到门 判断能不能开门 如果不能开门 入栈
if(map[x][y]>='A'&&map[x][y]<='E'&&curKey[map[x][y]-'A']<key[map[x][y]-'A'])
{
door[map[x][y]-'A'].x=x;
door[map[x][y]-'A'].y=y;
door[map[x][y]-'A'].exit=true;
return ;
}
vis[x][y]=true;
//找到一个钥匙 curkey[]+1
if(map[x][y]>='a'&&map[x][y]<='e')
curKey[map[x][y]-'a']++;
if(map[x][y]=='G')
{
result=true;
return ;
}
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
check();
}
//地图找完后 回到门前再次判断是否可以开门
void check()
{
for(int i=0;i<5;i++)
{
if(door[i].exit)
{
if(curKey[i]==key[i])
{
int x=door[i].x;
int y=door[i].y;
dfs(x+1,y);
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
}
}
}
int main()
{
while(~scanf("%d %d",&m,&n))
{
if(m==0&&n==0)
break;
memset(key,0,sizeof(key));
memset(map,0,sizeof(map));
memset(vis,false,sizeof(vis));
memset(&door,0,sizeof(&door));
memset(curKey,0,sizeof(curKey));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
char ch;
scanf(" %c",&ch);
map[i][j]=ch;
if(ch>='a'&&ch<='e')
key[ch-'a']++;
if(ch=='S')
st_x=i,st_y=j;
}
}
result=false;
dfs(st_x,st_y);
if(result)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}全部评论 (0)
还没有任何评论哟~