蓝桥杯备考：BFS最短路径之kotori迷宫

这道题打眼一看又是找最短路径，所以我们还是用BFS

我们还是老样子，定义方向向量，然后用dfs遍历可以走的路径 把每个点的最短路径都标上号

最后我们再遍历存储最短路径的二维数组，我们把走到的出口全部计起来，然后找出路径最短的出口 打印

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 35;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
char a[N][N];
int n, m, x, y;
int path[N][N];
typedef pair<int, int> PII;
void bfs()
{
	queue<PII> q;
	q.push({ x,y });
	path[x][y] = 0;
	while (q.size())
	{
		auto t = q.front(); q.pop();
		int px = t.first; int py = t.second;
		for (int i = 0; i <= 3; i++)
		{
			int x = px + dx[i]; int y = py + dy[i];
			if (x > n || x<1 || y>m || y < 1) continue;
			if (path[x][y] != -1) continue;
			if (a[x][y] == '*') continue;
			path[x][y] = path[px][py] + 1;
			if (a[x][y] != 'e') q.push({ x,y });

		}
	}
}
int main()
{
	memset(path, -1, sizeof path);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 'k')
			{
				x = i;
				y = j;
			}
		}
	}
	bfs();
	int cnt = 0, ret = 1e9;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (a[i][j] == 'e' && path[i][j] != -1)
			{
				ret = min(path[i][j], ret);
				cnt++;
			}
		}
	}
	if (cnt == 0) cout << -1 << endl;
	else
	{
		cout << cnt << " " << ret << endl;
	}

	return 0;
}