<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

给定一个 $N$ 行 $M$ 列的 $01$ 矩阵 $A$，$A\[i\]\[j\]$ 与 $A\[k\]\[l\]$ 之间的曼哈顿距离定义为：

$dist(A\[i\]\[j\],A\[k\]\[l\])=|i-k|+|j-l|$

输出一个 $N$ 行 $M$ 列的整数矩阵 $B$，其中：

$B\[i\]\[j\]=min_{1≤x≤N,1≤y≤M,A\[x\]\[y\]=1}⁡{dist(A\[i\]\[j\],A\[x\]\[y\])}$

输入格式

第一行两个整数 $N,M$。

接下来一个 $N$ 行 $M$ 列的 $01$ 矩阵，数字之间没有空格。

输出格式

一个 $N$ 行 $M$ 列的矩阵 $B$，相邻两个整数之间用一个空格隔开。

数据范围

$1 \\le N,M \\le 1000$

输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

思路

这道题就是求每一个点距离$1$的最短曼哈顿距离。
如果我们分别对每一个点求答案的话，肯定会超时，于是我们反向思考，直接从所有的$1$向整张图搜索。同时更新一下答案。

代码

#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 1010;
const int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};
int n,m;
bool g[N][N];
int dist[N][N];
void bfs () {
    queue <PII> q;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (g[i][j]) 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 < 1 || a > n || b < 1 || b > m || g[a][b] || dist[a][b]) continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            q.push ({a,b});
        }
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            char ch;
            cin >> ch;
            g[i][j] = ch - '0';
        }
    }
    bfs ();
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) cout << dist[i][j] << ' ';
        cout << endl;
    }
    return 0;
}