acwing173. 矩阵距离

题目

题解

多源bfs问题

#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
char g[N][N];
int n,m,dist[N][N];
PII q[N*N];
void bfs(){
    memset(dist,-1,sizeof dist);
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    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){
        PII t=q[hh++];
        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[++tt]={a,b};
        }
    }
}
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++)
            printf("%d ",dist[i][j]);
    cout<<endl;
    }
    return 0;
}