分析

• 本题中的1相当于超市，0相当于住户，需要求解每个住户距离最近的一个超市的距离。

• 1相当于超市，也是上图中的起点。代码实现的时候并不需要创建虚拟源点，只需要在最开始的时候将所有1的位置加入到队列中即可，然后执行BFS得到结果。

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
int dist[N][N];

void bfs() {

    memset(dist, -1, sizeof dist);

    // 起点放入队列
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1') {
                dist[i][j] = 0;
                q[++tt] = {i, j};
            }

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    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 < 1 || a > n || b < 1 || b > m) continue;
            if (dist[a][b] != -1) continue;

            dist[a][b] = dist[t.x][t.y] + 1;
            q[++tt] = {a, b};
        }
    }
}

int main() {

    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", g[i] + 1);

    bfs();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) printf("%d ", dist[i][j]);
        puts("");
    }

    return 0;
}