nyoj 82 迷宫寻宝（一） 【BFS】

本文主要是介绍nyoj 82 迷宫寻宝（一） 【BFS】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

一个叫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 <stdio.h>
#include <string.h>
#include <queue>
using namespace std;char map[25][25];
int vis[25][25];
int n, m;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
struct node{int x, y;
};
node st, en, dorpos[6]; //dorpos是记录门的位置
int key[6];
int dor[6];int limit(node s){return (s.x>=0&&s.x<n&&s.y>=0&&s.y<m&&map[s.x][s.y]!='X');
}int check(){  //检查所有的门是不是都被打开了，换句话说就是所有的钥匙是不是已经清0了。int i;for(i = 0; i< 5; i ++){if(key[i]) return false;}return true;
}int bfs(){queue<node > q;int i;q.push(st);vis[st.x][st.y] = 1;while( !q.empty()){node temp = q.front();q.pop();//vis[st.x][st.y] = 0;if(map[temp.x][temp.y] >= 'a'&&map[temp.x][temp.y] <= 'e'&&key[map[temp.x][temp.y]-'a'] > 0){key[map[temp.x][temp.y]-'a'] --;if(key[map[temp.x][temp.y]-'a'] == 0&&dor[map[temp.x][temp.y]-'a']  == 1){node in;in.x = dorpos[map[temp.x][temp.y]-'a'].x;in.y = dorpos[map[temp.x][temp.y]-'a'].y;if(map[in.x][in.y] == 'X'){q.push(in);}}}if(map[temp.x][temp.y]>='A'&&map[temp.x][temp.y] <= 'E'){  //判断门是不是被扫过if(key[map[temp.x][temp.y]-'A'] > 0){//dor[map[temp.x][temp.y]-'A'] = 0;map[temp.x][temp.y] = 'X';continue; 如果此时是门，那么后面的就走不动了}}if(temp.x == en.x&&temp.y == en.y&&check()) return true;map[temp.x][temp.y] = 'X';for(i = 0; i < 4; i ++){node w = temp;w.x += dx[i]; w.y+=dy[i];if(limit(w)&&!vis[w.x][w.y]){q.push(w);vis[w.x][w.y] = 1;}}}return false;
}int main(){while(scanf("%d%d", &n, &m) , n||m){memset(map, 0, sizeof(map));memset(vis, 0, sizeof(vis));memset(key, 0, sizeof(key));memset(dor, 0, sizeof(key));int i, j;for(i = 0; i < n; i ++){  //图的处理scanf("%s", map[i]);for(j = 0; j < m; j ++){if(map[i][j] == 'S'){st.x = i; st.y = j;}else if(map[i][j] == 'G'){en.x = i; en.y = j;}else if(map[i][j] >='a'&&map[i][j]<='e'){key[map[i][j]-'a']++;}else if(map[i][j] >= 'A'&&map[i][j] <= 'E'){dor[map[i][j]-'A'] = 1;dorpos[map[i][j]-'A'].x = i;dorpos[map[i][j] - 'A'].y = j;}}}int flag = bfs();if(flag) puts("YES");else puts("NO");}return 0;
}

这篇关于nyoj 82 迷宫寻宝（一） 【BFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---