北京信息科技大学第十一届程序设计竞赛D：kotori和迷宫（bfs）

https://ac.nowcoder.com/acm/contest/940/D
 

题目描述

kotori在一个n*m迷宫里，迷宫的最外层被岩浆淹没，无法涉足，迷宫内有k个出口。kotori只能上下左右四个方向移动。她想知道有多少出口是她能到达的，最近的出口离她有多远？

输入描述:

第一行为两个整数n和m，代表迷宫的行和列数 (1≤n,m≤30)

后面紧跟着n行长度为m的字符串来描述迷宫。'k'代表kotori开始的位置，'.'代表道路，'*'代表墙壁，'e'代表出口。保证输入合法。

输出描述:

若有出口可以抵达，则输出2个整数，第一个代表kotori可选择的出口的数量，第二个代表kotori到最近的出口的步数。（注意，kotori到达出口一定会离开迷宫）

若没有出口可以抵达，则输出-1。

示例1

输入

复制

6 8
e.*.*e.*
.**.*.*e
..*k**..
***.*.e*
.**.*.**
*......e

输出

复制

2 7

说明

可供选择坐标为[4,7]和[6,8]，到kotori的距离分别是8和7步。

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
#define N 50
char str[N][N];
int book[N][N];
struct date{
	int x;
	int y;
	int t;
}a, b;
int main()
{
	int n, m, i, j, ans, tx, ty, minn=9999999,temp=0;
	int next[4][2]={1,0, -1,0, 0,1, 0,-1};
	scanf("%d%d", &n, &m);
	for(i=0; i<n; i++)
		scanf("%s", str[i]);
	queue<date>q;
	for(i=0; i<n; i++)
	{
		for(j=0; j<m; j++)
			if(str[i][j]=='k')
			{
				temp=1;
				break;
			}
		if(temp==1)
			break;
	}
	a.x=i;
	a.y=j;
	a.t=0;
	q.push(a); book[i][j]=1;
	ans=0;
	while(!q.empty())
	{
		a=q.front();
		q.pop();
		if(str[a.x][a.y]=='e')
		{
			ans++;
			minn=min(minn, a.t);
			continue;
		}
		for(i=0; i<4; i++)
		{
			tx=a.x+next[i][0];
			ty=a.y+next[i][1];
			if(tx<0 || ty<0 || tx>=n || ty>=m)
				continue;
			if(str[tx][ty]!='*' && book[tx][ty]==0)
			{
				b.x=tx;
				b.y=ty;
				b.t=a.t+1;
				q.push(b);	
			}
			book[tx][ty]=1;	
		} 
	}
	if(minn==9999999)	
		printf("-1
");
	else
		printf("%d %d
", ans, minn);
	return 0;
}