最短路模型，即求从起点到终点的最短路径，我们可以选择dijkstra，spfa等等，在这里我们可以利用宽搜(bfs)的特性来求，因为bfs是一层一层的向外扩展的，所以当我们第一次遍历到终点时，所在的层数即为起点到终点的最短路径。
多源bfs，顾名思义，多个起点的bfs，与一般的bfs不同的地方在于根据题目要求，将多个起点在初始时全部加入队列即可，后续遍历和普通bfs没什么不同。
给定一个 n×n 的二维数组，如下所示：
int maze[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,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。
输出格式
输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。
按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)(0,0)，右下角坐标为 (n−1,n−1)。
数据范围
0≤n≤1000
输入样例：
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
输出样例：
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4思路：简单bfs，要求输出路径，为了方便记录路径，我们从终点出发到起点，开辟一个二维数组记录一下每个点的前驱点即可
#include <iostream> #include <cstring> #include <algorithm> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010; int n; int g[N][N]; PII q[N * N]; PII pre[N][N];//每个点的上一步 int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; void bfs(int sx, int sy) { int hh = -1, tt = -1; q[ ++ tt ] = {sx, sy}; memset(pre, -1, sizeof pre); pre[sx][sy] = {0, 0}; while (hh <= tt) { PII t = q[ ++ hh]; for(int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if(a < 0 || a >= n || b < 0 || b >= n || g[a][b] || pre[a][b].x != -1) continue; q[ ++ tt] = {a, b}; pre[a][b] = t; } } } int main() { cin >> n; for(int i = 0; i < n; i ++ ) for(int j = 0; j < n; j ++ ) cin >> g[i][j]; bfs(n - 1, n - 1); PII end = {0, 0}; while (true) { printf("%d %d\n", end.x, end.y); if(end.x == n - 1 && end.y == n - 1) break; end = pre[end.x][end.y]; } return 0; }
给定一个 N 行 M 列的 0101 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个 N 行 M 列的整数矩阵 B，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数 N,M。
接下来一个 N 行 M 列的 0101 矩阵，数字之间没有空格。
输出格式
一个 N 行 M 列的矩阵 B，相邻两个整数之间用一个空格隔开。
数据范围
1≤N,M≤1000
输入样例：
3 4
0001
0011
0110
输出样例：
3 2 1 0
2 1 0 0
1 0 0 1思路：将多个起点一起加入队列然后和普通bfs一样宽搜即可
#include <iostream> #include <cstring> #include <algorithm> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010; int n, m; char A[N][N]; int B[N][N]; void bfs() { int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; memset(B, -1, sizeof B); queue<PII> q; for(int i = 0; i < n; i ++ ) for(int j = 0; j < m; j ++ ) if(A[i][j] == '1') { B[i][j] = 0; q.push({i, j}); } while (q.size()) { PII t = q.front(); q.pop(); for(int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if(a < 0 || a >= n || b < 0 || b >= m) continue; if(B[a][b] != -1) continue; B[a][b] = B[t.x][t.y] + 1; q.push({a, b}); } } } int main() { cin >> n >> m; for(int i = 0; i < n; i ++ ) cin >> A[i]; bfs(); for(int i = 0; i < n; i ++ ) { for(int j = 0; j < m; j ++ ) cout << B[i][j] << " "; puts(""); } return 0; }
