思路分析

一：队列里面的单调性：

距离起点最近的点总是在队头，类似 x x x x1 x1 x1..．的形式，其中ｘ距离起点的距离小于x1，两段性指的是队列中任意时刻最多只有两层的元素

二：本题的做法是把所有的起点（==‘1’）先放入队列，再按照正常的bfs一样去更新

三：算法的正确性：

1：可以想像所有起点的前面有一个虚拟节点，这个虚拟节点到其他所有起点的距离为0，现在要求的问题是所有其他点到这个虚拟节点的最小距离，做这个问题的时候，第一步要做的就是先把虚拟节点周围的所有未访问过的节点放入队列，这一步就对应了下面的代码

queue<pair<int, int>> q;
    for(int i = 0;i < n;++i)
        for(int j = 0;j < m;++j)
            if(g[i][j] == '1'){
                q.push({i, j});
                dist[i][j] = 0;
            }

2: 接下来做的就应该是再用刚才扩展的这一层再去扩展下一层

while(q.size()){
        auto t = q.front();q.pop();
        for(int i = 0;i < 4;++i){
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(dist[a][b] != -1) continue;
            dist[a][b] = dist[t.first][t.second] + 1;
            q.push({a, b});
        }        
    }

四：核心思想，就是把这个多个起点的问题转化为一个起点的bfs问题，再按照一个起点的bfs解题思路（扩展第一层，在扩展第二层…），只不过这里的扩展第一层写成另一种形式了

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

char g[N][N];
int dist[N][N];
int n, m;

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

void bfs(){
    memset(dist, -1, sizeof dist);
    queue<pair<int, int>> q;
    for(int i = 0;i < n;++i)
        for(int j = 0;j < m;++j)
            if(g[i][j] == '1'){
                q.push({i, j});
                dist[i][j] = 0;
            }
    while(q.size()){
        auto t = q.front();q.pop();
        for(int i = 0;i < 4;++i){
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(dist[a][b] != -1) continue;
            dist[a][b] = dist[t.first][t.second] + 1;
            q.push({a, b});
        }        
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0;i < n;++i)
        cin >> g[i];
    bfs();
    for(int i = 0;i < n;++i){
        for(int j = 0;j < m;++j)
            cout << dist[i][j] << " ";
        cout << endl;
    }
    return 0;
}