迷宫寻宝（一）
时间限制：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
好题。做了两天才过。。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using std::vector;
using std::queue;
struct Node{
int x, y;
} start;
queue<Node> Q;
vector<Node> door[5];
int m, n, tkey[5], key[5], vis[22][22];
char map[22][22];
const int mov[][2] = {0, 1, 0, -1, -1, 0, 1, 0};
bool checkOpenDoor(char ch){
return key[ch - \'A\'] == tkey[ch - \'A\'];
}
//check函数的作用：1、推断点是否越界 2、推断是否已经訪问或为墙壁
//3、是否为钥匙，若是则更新钥匙且推断是否能打开门。如能则将之前入栈
//的门入队 4、推断是否为门。若是再推断是否能打开，若不能则入栈且返回0
bool check(Node t){
if(t.x < 0 || t.y < 0 || t.x >= m || t.y >= n)
return 0;
if(vis[t.x][t.y] || map[t.x][t.y] == \'X\')
return 0;
char ch = map[t.x][t.y];
if(ch >= \'a\' && ch <= \'e\'){
++key[ch - \'a\'];
while(key[ch - \'a\'] == tkey[ch - \'a\'] && !door[ch - \'a\'].empty()){
Q.push(door[ch - \'a\'].back());
door[ch - \'a\'].pop_back();
}
}
if(ch >= \'A\' && ch <= \'E\' && !checkOpenDoor(ch)){
door[ch - \'A\'].push_back(t);
vis[t.x][t.y] = 1;
return 0;
}
return 1;
}
void BFS(){
for(int i = 0; i < 5; ++i)
door[i].clear();
while(!Q.empty()) Q.pop();
vis[start.x][start.y] = 1;
Q.push(start);
Node temp, now;
while(!Q.empty()){
now = Q.front(); Q.pop();
for(int i = 0; i < 4; ++i){
temp = now;
temp.x += mov[i][0];
temp.y += mov[i][1];
if(check(temp)){
if(map[temp.x][temp.y] == \'G\'){
puts("YES"); return;
}
vis[temp.x][temp.y] = 1;
Q.push(temp);
}
}
}
puts("NO");
}
int main(){
char ch;
while(scanf("%d%d", &m, &n), m || n){
memset(tkey, 0, sizeof(tkey));
memset(key, 0, sizeof(key));
memset(vis, 0, sizeof(vis));
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
ch = getchar();
if(ch == \' \' || ch == \'\n\'){
--j; continue;
}
map[i][j] = ch;
if(ch >= \'a\' && ch <= \'e\')
++tkey[ch - \'a\'];
else if(ch == \'S\'){
start.x = i; start.y = j;
}
}
}
BFS();
}
return 0;
} 