AcWing 173. 矩阵距离(多源bfs)
原题链接
简单
#include<iostream>
#include<queue>
using namespace std;
const int N=1e3+5;
int n,m,dist[N][N],dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool flag[N][N];
char G[N][N];
void bfs(){
queue<pair<int,int>>q;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(G[i][j]=='1') {flag[i][j]=true; q.push({i,j});}
while(!q.empty()){
auto t=q.front();
int x=t.first,y=t.second;
q.pop();
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
if(!flag[xx][yy]){
flag[xx][yy]=true;
dist[xx][yy]=dist[x][y]+1;
q.push({xx,yy});
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>G[i][j];
bfs();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}