记录编号	203867	评测结果	AAAAAAAAAAAAAAAA
题目名称	[POI 1999] 位图	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.342 s
提交时间	2015-11-03 19:14:29	内存使用	0.51 MiB

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200;
const int gx[4]={-1,0,1,0};
const int gy[4]={0,1,0,-1};
char t[MAXN];
bool ok[MAXN][MAXN];
int dis[MAXN][MAXN],n,m;
struct At{int x,y,d;};
queue<At>q;
inline void print(){
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			printf("%d ",dis[i][j]);
		}
		puts("");
	}
}
inline int ABS(int a){return a<0?-a:a;}
inline int dist(int x,int y,int xx,int yy){return ABS(x-xx)+ABS(y-yy);}
inline int Min(int a,int b){return a<b?a:b;}
inline void Bfs(){
	while(!q.empty()){
		int qx=q.front().x,qy=q.front().y,ci=q.front().d;q.pop();
		for(int i=0,temp;i<4;++i) {
			int nx=qx+gx[i],ny=qy+gy[i];
			if(nx<1||ny<1||nx>n||ny>m||ok[nx][ny]) continue;
			temp=dist(qx,qy,nx,ny);if(dis[nx][ny]>temp+ci){
				dis[nx][ny]=temp+ci;
                q.push((At){nx,ny,ci+temp});
			}
		}
	}
}
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	memset(dis,0x3f,sizeof(dis));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%s",t+1);
		for(int j=1;j<=m;++j) {
			if(t[j]=='1') {
				ok[i][j]=1;//白棋子
			}
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			if(ok[i][j]==1){
				dis[i][j]=0;
				q.push((At){i,j,0});
				Bfs();
			}
		}
	}
	print();
	return 0;
}