文章目录
1. 题目来源
链接:173. 矩阵距离
2. 题目解析
一般来讲,bfs
求最短路、最短距离只有一个起点,那么我们初始化就只往队列中添加这个起点,让其分层拓展即可。
但是,也可以有多个起点,且性质相同。等价来看就可以将多个起点初始全部放入队列,让其当做第一层,第 0 层可以视为一个虚拟源点,它连接到这些起点且花费为 0。 这个和图论中的概念相同。
多源 bfs
就是初始化将起点(源点)全部加入队列,并进行相应初始化,剩余操作和普通 bfs
求最短路一致。
时间复杂度: O ( n m ) O(nm) O(nm)
空间复杂度: O ( n m ) O(nm) O(nm)
好题,多观察观察数据
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 1005;
int n, m;
char g[N][N];
int dist[N][N];
PII q[N * N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs() {
int hh = 0, tt = -1;
memset(dist, -1, sizeof dist);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '1') {
q[ ++ tt ] = {i, j};
dist[i][j] = 0;
}
while (hh <= tt) {
auto t = q[hh ++ ];
int x = t.first, y = t.second;
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (dist[a][b] != -1) continue;
dist[a][b] = dist[x][y] + 1;
q[ ++ tt ] = {a, b};
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) // 不要 %d,直接读入一个整数了...scanf("%1d", &g[i][j])也可...
scanf("%s", g[i]);
bfs();
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ )
printf("%d ", dist[i][j]);
puts("");
}
return 0;
}