acwing173. 矩阵距离（多源bfs）

给定一个 NN 行 MM 列的 0101 矩阵 AA，A[i][j]A[i][j] 与 A[k][l]A[k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l])=|i−k|+|j−l|dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个 NN 行 MM 列的整数矩阵 BB，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1⁡dist(A[i][j],A[x][y])

输入格式

第一行两个整数 N,MN,M。
接下来一个 NN 行 MM 列的 0101 矩阵，数字之间没有空格。

输出格式

一个 NN 行 MM 列的矩阵 BB，相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤10001≤N,M≤1000

输入样例：

3 4 0001 0011 0110

输出样例：

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

#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 dist[N][N];
char g[N][N];
PII q[N*N];
int n,m;
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
void bfs() {
    memset(dist,-1,sizeof dist);
    int hh = 0, tt = -1;
    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++];
        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 (dist[a][b] != -1) continue;
            q[++tt] = {a,b};
            dist[a][b] = dist[t.x][t.y] + 1;
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) scanf("%s",&g[i]);
    bfs();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) 
            cout << dist[i][j] << ' ';
        puts("");
    }
    return 0;
}