多源bfs

C++ 代码

#include <iostream>
#include <queue>
using namespace std;

using PII = pair<int, int>;
const int N = 1010;
int n, m;
int d[N][N];
queue<PII> q;

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

void bfs(){ // 多源bfs
    while(!q.empty()){
        auto &t = q.front();
        int a = t.first, b = t.second;
        q.pop();
        for(int i = 0; i < 4; ++ i){
            int x = a + dx[i], y = b + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && d[x][y] == -1){
                d[x][y] = d[a][b] + 1;
                q.push({x , y});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j){
            char c;
            cin >> c;
            d[i][j] = -1;
            if(c == '1'){
                q.push({i , j}); //把所有的1都入队
                d[i][j] = 0;
            } 
        }

    bfs();       

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

    return 0;
}