记录编号	559191	评测结果	AAAAAAAAAAAAAAAA
题目名称	[POI 1999] 位图	最终得分	100
用户昵称	城南花已开	是否通过	通过
代码语言	C++	运行时间	2.989 s
提交时间	2021-02-19 23:40:20	内存使用	2.86 MiB

# include <iostream>
# include <cstdio>
using namespace std;
int n,m,tail,s=0,bit1[200][200],bit3[40000],bit4[40000],x1[5]={0,0,1,0,-1},y1[5]={0,1,0,-1,0};
bool bit2[200][200];
char bit0[200][200];
int bfs(int x,int y){
	int head=0,i;
	tail=1;
	bit3[1]=x;
	bit4[1]=y;
	do{
		head++;
		for(i=1;i<=4;i++){
			if(bit3[head]+x1[i]>=1&&bit3[head]+x1[i]<=n&&bit4[head]+y1[i]>=1&&bit4[head]+y1[i]<=m){
				if(bit0[bit3[head]+x1[i]][bit4[head]+y1[i]]!='1'&&bit2[bit3[head]+x1[i]][bit4[head]+y1[i]]==true){
					tail++;
					bit3[tail]=bit3[head]+x1[i];
					bit4[tail]=bit4[head]+y1[i];
					bit2[bit3[tail]][bit4[tail]]=false;
					if(bit1[bit3[head]][bit4[head]]+1<bit1[bit3[tail]][bit4[tail]]){
					    bit1[bit3[tail]][bit4[tail]]=bit1[bit3[head]][bit4[head]]+1;	
					}
				}
			}
		}
	}while(head<tail);
}
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >>bit0[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			bit1[i][j]=999999;
			bit2[i][j]=true;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(bit0[i][j]=='1'){
				bit1[i][j]=0;
				bit2[i][j]=false;
				bfs(i,j);
				for(int u=1;u<=tail;u++){
					bit3[u]=0;
					bit4[u]=0;
				}
				for(int u=1;u<=n;u++){
					for(int v=1;v<=m;v++){
						bit2[u][v]=true;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout <<bit1[i][j]<<" ";
		}
		cout <<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}