【BFS】（代码详解）

全面学习BFS的可以参照以下路径，本文章只附上部分代码的解释作为学习记录共勉（星星眼）
原文链接：https://blog.csdn.net/m0_62881629/article/details/125072287

给定一个 n×mn×m 的二维整数数组，用来表示一个迷宫，数组中只包含 00 或 11，其中 00 表示可以走的路，11 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)(1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)(n,m) 处，至少需要移动多少次。

数据保证 (1,1)(1,1) 处和 (n,m)(n,m) 处的数字为 00，且一定至少存在一条通路。

输入格式
第一行包含两个整数 nn 和 mm。
接下来 nn 行，每行包含 mm 个整数（00 或 11），表示完整的二维数组迷宫。

输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤1001≤n,m≤100

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：

8

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int, int>PII;
const int N = 110;

int n, m;
int  g[N][N]; //存储地图
int  d[N][N]; // 储存每一个点到起点的距离
PII  q[N * N]; //手动定义一个队列

int bfs() {
	int h = 0, t = 0; // 队头和队尾
	q[0] = {0, 0}; // 将起点坐标放入队列的第一个位置
	memset(d, -1, sizeof(d)); 
    // 将所有的d数组元素初始化为-1，表示未访问过
	d[0][0] = 0; // 起点到起点的距离为0

	int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 
/*当 i = 0 时，表示向上移动，对应的偏移量为 (dx[0], dy[0]) = (-1, 0)，即在行上减1，列上不变；
当 i = 1 时，表示向右移动，对应的偏移量为 (dx[1], dy[1]) = (0, 1)，即在行上不变，列上加1；
当 i = 2 时，表示向下移动，对应的偏移量为 (dx[2], dy[2]) = (1, 0)，即在行上加1，列上不变；
当 i = 3 时，表示向左移动，对应的偏移量为 (dx[3], dy[3]) = (0, -1)，即在行上不变，列上减1。*/

while (h <= t) { // 队列不为空时执行循环
   	auto t = q[h++]; 
    for (int i = 0; i < 4; i++) { // 遍历四个方向
		*int x = t.first + dx[i], y = t.second + dy[i]; 
  // t.first 表示当前位置的 x 坐标,t.second 表示当前位置的 y 坐标
  //dx[i] 表示在第 i 个方向上 x 坐标的偏移量,dy[i] 表示在第 i 个方向上 y 坐标的偏移量

// 判断下一个位置是否在边界内、在地图内、没有走过
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
// g[x][y] == 0 判断位置 (x, y) 是否可通行，其中 g 可能是一个二维数组或向量,d[x][y] == -1 判断位置 (x, y) 是否未被访问过
		d[x][y] = d[t.first][t.second] + 1; 
    	// 更新到达下一个位置的步数
		q[++tt] = {x, y}; // 将下一个位置加入队列
			}
		}
	}
	return d[n - 1][m - 1]; // 返回终点到起点的最短距离
}
int main() {
	cin >> n >> m;
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
		}
	}
 
	cout << bfs() << endl;
	return 0;

1. 初始化起点坐标 (0, 0)，将其加入队列 q 中，并初始化距离数组 d 为未访问状态，起点到起点的距离为 0。
2. 定义四个方向的偏移量数组 dx 和 dy，分别表示上、右、下、左四个方向的移动情况。
3. 在队列不为空时，不断从队列中取出坐标 (x, y) 进行处理，然后遍历四个方向，判断是否可以向上、右、下、左四个方向移动，即判断下一个位置是否在边界内、在地图内、可通行且未被访问过。
4. 如果满足条件，则更新到达下一个位置的步数，并将下一个位置加入队列。
5. 重复以上步骤，直到遍历完所有可达的位置或找到终点 (n-1, m-1)。
6. 最终返回终点到起点的最短距离