1101. 献给阿尔吉侬的花束(bfs找最短路径)

题目：

1101. 献给阿尔吉侬的花束 - AcWing题库

?

?

输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例：

5
1
oop!

思路：bfs宽搜?

用队列实现bfs。踢出队列头，并在队列尾插入与对头相关的xxx(往往是相邻点)。直至队列为空。这个过程相当于逐行遍历宽度优先搜索树。可以用于求最短路径。?

拓展补充：

BFS（Breadth-First Search，广度优先搜索）是一种图算法，用于遍历或搜索图中的节点。它从图的起始节点开始，逐层地访问其相邻节点，直到找到目标节点或遍历完整个图。

BFS通常使用队列来实现，起始节点首先被放入队列中，然后依次访问其相邻节点，并将这些相邻节点加入队列。接着从队列中取出下一个节点，重复上述过程，直到队列为空为止。

BFS的特点是能够找到起始节点到目标节点的最短路径，因为它先访问离起始节点最近的节点，然后依次向外扩展。这使得BFS在寻找最短路径或最短距离的问题上非常有效。

BFS也可以用于检测图中的环路、连通性、拓扑排序等问题。它是一种简单而且常用的图算法，被广泛应用于计算机科学领域的各种问题中。

代码：?

#include<iostream>
#include<cstdio>
#include<cstring>//memset头文件
#include<queue>
using namespace std;
typedef pair<int, int>PII;
#define x first
#define y second
PII Start, End;//表示起点和终点
const int N = 210;
int m, n;//表示矩阵行列
int dist[N][N];//表示距离起点start的距离（赋初值为-1,可以用于判重）
char p[N][N];//表示矩阵某点坐标

int bfs(PII Start, PII End)
{
	memset(dist, -1, sizeof dist);//设距离起点初始值为-1
	dist[Start.x][Start.y] = 0;
	queue<PII>q;//用队列实现宽搜bfs
	q.push(Start);
	while (q.size()) {
		PII t = q.front();//取对列头
		q.pop();//将对头踢出队列
		int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 };
		for (int i = 0; i < 4; i++) {
			int x = t.x + dx[i]; int y = t.y + dy[i];
			//不合规走法
			if (x < 0 || x >= m || y < 0 || y >= n)continue;//越界
			if (p[x][y] == '#')continue;//路障
			if (dist[x][y] != -1)continue;//之前已经遍历过
			//合规走法
			dist[x][y] = dist[t.x][t.y] + 1;//在队列头t的基础上走出一步，距离+1
			q.push({ x,y });//将合规走法的坐标点加入队列尾部
			if (End == make_pair(x, y))return dist[x][y];
		}
	}
	return -1;//表示走到不能走了都没有找到End，即无法到达
}

int main()
{
	int T;
	cin >> T;
	while (T--) {
		scanf("%d%d", &m, &n);
		for (int i = 0; i < m; i++)scanf("%s", &p[i]);//按行输入
		
		for(int i=0;i<m;i++)
			for (int j = 0; j < n; j++) {
				if (p[i][j] == 'S')Start = { i,j };
				else if (p[i][j] == 'E')End = { i,j };
			}
		int distance = bfs(Start, End);
		if (distance == -1)cout << "oop!" << endl;
		else cout << distance<<endl;
	}

}

?