- 描述
-
一个叫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
- 来源
- POJ月赛改编
- 上传者
- 张云聪
-
#include <iostream> #include <cstring> using namespace std; char map[23][23]; int visit[23][23]; int yao[10]; int n, m; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int isagain; int flag = 0; int dfs(int x, int y){ if(map[x][y] == 'G'){ flag = 1; return 1; } for(int i = 0; i < 4; i++){ int xx = x + dx[i]; int yy = y + dy[i]; if(xx >= 0 && xx < n && yy >= 0 && yy < m){ if(!visit[xx][yy]){ visit[xx][yy] = 1; if(map[xx][yy] == '.'){ if(dfs(xx, yy)) return 1; } else if(map[xx][yy] >= 'a' && map[xx][yy] <= 'z'){ yao[map[xx][yy] - 'a']--; //找到对应钥匙了，相当于打开此门所需要的钥匙减一 if(yao[map[xx][yy]] == 0){ //可以打开对应的门了 isagain = 1; //所以可以给他一次重新搜索的机会 } map[xx][yy] = '.'; if(dfs(xx, yy)) return 1; } else if(map[xx][yy] >= 'A' && map[xx][yy] <= 'E'){ //刚开始写成了A到G，所以永远到不了G的判断 if(yao[map[xx][yy] - 'A'] == 0){ // cout << "open: " << map[xx][yy] << endl; map[xx][yy] = '.'; if(dfs(xx, yy)) return 1; } } else if(map[xx][yy] == 'G'){ // cout << "G" << endl; if(dfs(xx, yy)) return 1; } visit[xx][yy] = 0; } } } return 0; } int main(){ std::ios::sync_with_stdio(false); while(cin >> n >> m){ memset(visit, 0, sizeof(visit)); memset(yao, 0, sizeof(yao)); if((n == 0 && m == 0)) break; int sx, sy; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> map[i][j]; if(map[i][j] >= 'a' && map[i][j] <= 'z'){ yao[map[i][j] - 'a']++; //记录每个门所需要的钥匙 } else if(map[i][j] == 'S'){ //记录起点 sx = i, sy = j; } } } flag = 0; isagain = 1; while(isagain){ //可能可以打开门，重新尝试一次 isagain = 0; memset(visit, 0, sizeof(visit)); //因为dfs里面有许多return,打断了还原0 visit[sx][sy] = 1; flag = dfs(sx, sy); if(flag) break; } if(flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; } /* 5 5 SXaXG .X.X. .X.X. .X.XA ..... 5 5 aE..S bXX.c XX.CX GBA.B XXe.e 5 5 a...a XX.XX bXSXG .XAXB ..... 5 5 .X.XG Sa..A .b.Xc XX..B bC... 5 5 .X.XG Sb..B .b.Xc XX..B bC... 1 10 S.aAbBcC.G 0 0 */