迷宫寻宝（一）
时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
-
一个叫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找不到宝藏。
- 样例输入
-
4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0 - 样例输出
-
YES
NO
思路比较简单，但是实现起来比较罗嗦，这题广度优先搜索比较有优势，先确定各种钥匙有几个，这个在输入的时候就可以记录一下，还有记录下各锁的位置，然后广搜过程中如果集齐了某种钥匙，就把锁的位置放入队列，直到队列为空也没找到重点，那么就是no，如果空之前就找到了，那就是yes
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; char map[23][23];
bool step[23][23];
int key[5]; typedef struct NODE
{
int x, y;
}Node;
queue<Node> q;
Node door[5];
bool hash[5];
bool flag[5];
int t;
bool bfs()
{
Node node;
Node new_node;
while(!q.empty())
{
node = q.front();
q.pop();
if(map[node.x][node.y] >= 'A' && map[node.x][node.y] <= 'E')
{
hash[map[node.x][node.y] - 'A'] = 1;
if(key[map[node.x][node.y] - 'A'] > 0 || flag[map[node.x][node.y] - 'A'] == 0)
{
step[node.x][node.y] = 1;
continue;
}
}
else if(map[node.x][node.y] >= 'a' && map[node.x][node.y] <= 'e')
{
key[map[node.x][node.y] - 'a'] --;
if(hash[map[node.x][node.y] - 'a'] == 1 && key[map[node.x][node.y] - 'a'] <= 0)
{
map[door[map[node.x][node.y] - 'a'].x][door[map[node.x][node.y] - 'a'].y] = '.';
new_node.x = door[map[node.x][node.y] - 'a'].x;
new_node.y = door[map[node.x][node.y] - 'a'].y;
q.push(new_node);
}
}
else if(map[node.x][node.y] == 'G')
{
while(!q.empty())
{
q.pop();
}
return 1;
}
if(map[node.x + 1][node.y] != 'X' && step[node.x + 1][node.y] != 1)
{
new_node.x = node.x + 1;
new_node.y = node.y;
q.push(new_node);
step[node.x + 1][node.y] = 1;
}
if(map[node.x - 1][node.y ] != 'X' && step[node.x - 1][node.y ] != 1)
{
new_node.x = node.x - 1;
new_node.y = node.y;
q.push(new_node);
step[node.x - 1][node.y ] = 1;
}
if(map[node.x][node.y + 1] != 'X' && step[node.x][node.y + 1] != 1)
{
new_node.x = node.x;
new_node.y = node.y + 1;
q.push(new_node); step[node.x][node.y + 1] = 1;
}
if(map[node.x][node.y - 1] != 'X' && step[node.x][node.y - 1] != 1)
{
new_node.x = node.x;
new_node.y = node.y - 1;
q.push(new_node); step[node.x][node.y - 1] = 1;
}
}
return 0;
}
int main()
{
int n, m;
while(scanf("%d %d", &n, &m) != EOF)
{
getchar();
if(m == n && n == 0)
break;
memset(map, 'X', sizeof(map));
memset(step, '0', sizeof(step));
key[0] = key[1] = key[2] = key[3] = key[4] = 0;
door[0].x = door[0].y = door[1].x = door[1].y = door[2].x = door[2].y = door[3].x = door[3].y = door[4].x = door[4].y =0;
hash[0] = hash[1] = hash[2] = hash[3] = hash[4] = 0;
flag[0] = flag[1] = flag[2] = flag[3] = flag[4] = 0;
int i, j;
int start_x, start_y;
t = 1;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
char ch;
ch = getchar();
if(ch == ' ' || ch == '\n')
{
j--;
continue;
}
map[i][j] = ch;
if(map[i][j] >= 'a' && map[i][j] <= 'e')
{
key[map[i][j] - 'a']++;
flag[map[i][j] - 'a'] = 1;
}
else if(map[i][j] >= 'A' && map[i][j] <= 'E')
{
door[map[i][j] - 'A'].x = i;
door[map[i][j] - 'A'].y = j;
}
else if(map[i][j] == 'S')
{
start_x = i;
start_y = j;
}
}
getchar();
}
Node node;
node.x = start_x;
node.y = start_y;
q.push(node);
step[start_x][start_y] = 1;
if(bfs() == 1)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}