C++(g++ 7.5.0) 解法, 执行用时: 203ms, 内存消耗: 14724K, 提交时间: 2022-10-13 20:29:10

#include<bits/stdc++.h>

using namespace std;
struct node{
	int x,y;
	int cnt;
};
const int maxn=1010;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m;
int a[maxn][maxn],b[maxn][maxn];
int main(){
	scanf("%d%d",&n,&m);
	queue<node> q;
	memset(b,-1,sizeof(b));
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=m;j++){
			a[i][j]=s[j-1]-'0';
			if(a[i][j]==1) q.push({i,j,0}),b[i][j]=0;
		}
	}
	while(!q.empty()){
		node _=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int tx=_.x+dx[i],ty=_.y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
				if(b[tx][ty]==-1){
					b[tx][ty]=b[_.x][_.y]+1;
					q.push({tx,ty,b[tx][ty]});
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			printf("%d ",b[i][j]);
		}
		puts("");
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 109ms, 内存消耗: 19684K, 提交时间: 2020-03-18 20:40:13

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

struct node
{
	int x,y,h;
}Q[3000005];
int n,m,V[1005][1005],dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char R[1005];
int main()
{
    int i,j,x,y,h,X,Y,r=0,f=0;
	scanf("%d%d",&n,&m);
	memset(V,0x3f,sizeof(V));
    for(i=0;i<n;i++)
    {
    	scanf("%s",R);
    	for(j=0;j<m;j++)if(R[j]=='1')Q[r].x=i,Q[r].y=j,Q[r++].h=V[i][j]=0;
	}
	while(r!=f)
	{
		x=Q[f].x,y=Q[f].y,h=Q[f++].h;
		for(i=0;i<4;i++)
		{
			X=x+dx[i],Y=y+dy[i];
			if(X<0||X>=n||Y<0||Y>=m||V[X][Y]<=h+1)continue;
			V[X][Y]=h+1,Q[r].x=X,Q[r].y=Y,Q[r++].h=h+1;
		}
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)printf("%d ",V[i][j]);
		printf("\n");
	}
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 170ms, 内存消耗: 10016K, 提交时间: 2020-05-15 22:28:39

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int g[N][N],n,m,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
string ch[N];
struct node
{
	int x,y;
};
queue<node> q;
int main()
{
	memset(g,-1,sizeof g);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>ch[i];
		for(int j=0;j<m;j++)
		if(ch[i][j]=='1'){
			g[i][j]=0;
			q.push({i,j});
		}
	}
	while(q.size())
	{
		auto t=q.front();q.pop();
		for(int i=0;i<4;i++)
		{
			int x=t.x+dx[i],y=t.y+dy[i];
			if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==-1)
			{
				g[x][y]=g[t.x][t.y]+1;
				q.push({x,y});
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		printf("%d ",g[i][j]);
		printf("\n");
	}
	return 0;
 }