【问题描述】
kotori在一个n*m迷宫里，迷宫的最外层被岩浆淹没，无法涉足，迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的，最近的出口离她有多远？
【输入】
第一行为两个整数n和m，代表迷宫的行和列数 (1≤n,m≤30)
后面紧跟着n行长度为m的字符串来描述迷宫。'k'代表kotori开始的位置，'.'代表道路，'*'代表墙壁，'e'代表出口。保证输入合法。
【输出】
若有出口可以抵达，则输出2个整数，第一个代表kotori可选择的出口的数量，第二个代表kotori到最近的出口的步数。（注意，kotori到达出口一定会离开迷宫）
若没有出口可以抵达，则输出-1。
【样例输入】
6 8
e.*.*e.*
.**.*.*e
..*k**..
***.*.e*
.**.*.**
*......e
【样例输出】
2 7
【样例解释】
可供选择坐标为[4,7]和[6,8]，到kotori的距离分别是8和7步。
PS : 这个是本校OJ的题，还是今年的校赛的题，不过需要校园网才能访问。http://acm.bistu.edu.cn/acm/submit.jsp?problemID=2906&pageNo=1&pages=0 这个题当时我虽然过了，但是却花了我不少时间，提交了9次才能过，9次。。。。现在重新做这个题，也还是提交4次才过。。。emmmmm
这个是BFS题，求出口的个数并不难（虽然碰上过小坑），但是关键是如何求起点到最近的出口的步长，我的思路是建立一个二维数组，然后统计。
C++代码：
#include<iostream> #include<algorithm> #include<queue> #include<cstring> #include<cstdio> using namespace std; typedef pair<int,int> pii; int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; const int maxn = 31; bool vis[maxn][maxn]; char str[maxn][maxn]; int dis[maxn][maxn]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i = 0; i < n; i++){ scanf("%s",str[i]); } memset(dis,0,sizeof(dis)); int nums = 0; int flagi = 0,flagj = 0; memset(vis,false,sizeof(vis)); queue<pii> q; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(str[i][j] == 'k'){ q.push(make_pair(i,j)); dis[i][j] = 0; vis[i][j] = true; while(!q.empty()){ pii t = q.front(); q.pop(); for(int l = 0; l < 4; l++){ int x = t.first + dx[l]; int y = t.second + dy[l]; if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && str[x][y] != '*'){ vis[x][y] = true; dis[x][y] = dis[t.first][t.second] + 1; //这两行代码是在下面的两个语句括号内都必须运行的，在‘e’上也要标记已经访问过的。emmm，连续提交4次中，前3次的错误的原因在于这个 if(str[x][y] == '.'){ q.push(make_pair(x,y)); } else if(str[x][y] == 'e'){ nums++; if(nums == 1){ //得到最近的出口的位置，便于得到起点但最近的出口的步长。 flagi = x; flagj = y; } else continue; } } } } } } } if(nums == 0) printf("-1\n"); else printf("%d %d\n",nums,dis[flagi][flagj]); return 0; }
转载于:https://www.cnblogs.com/Weixu-Liu/p/10884084.html
相关资源：图的dfs和bfs遍历-c语言版