C++ 代码
多源bfs
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=1e3+10;
PII q[N*N];
int g[N][N];
int dist[N][N];
int n,m;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void bfs()
{
memset(dist,-1,sizeof(dist));
int hh=0,tt=-1;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(g[i][j])
{
q[++tt]={i,j};
dist[i][j]=0;
}
}
}
while(hh<=tt)
{
auto 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||dist[a][b]!=-1)continue;
q[++tt]={a,b};
dist[a][b]=dist[t.first][t.second]+1;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
scanf("%1d",&g[i][j]);
}
bfs();
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
printf("%d ",dist[i][j]);
printf("\n");
}
return 0;
}