记录编号	6831	评测结果	AAAAAAAAAAAAAAAA
题目名称	[POI 1999] 位图	最终得分	100
用户昵称	zqzas	是否通过	通过
代码语言	C++	运行时间	0.447 s
提交时间	2008-11-04 20:53:21	内存使用	15.52 MiB

#include <iostream>

#define MAXN 1000
#define INF 9999999

using namespace std;

const int Dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,m,data[MAXN][MAXN],dis[MAXN][MAXN],que[MAXN*MAXN][2];

void bfs()
{
	int d,x,y,a,b,head=-1,tail=-1;
	bool visit[MAXN][MAXN]={{0}};
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (data[i][j]==1)
			{
				dis[i][j]=0;
				visit[i][j]=1;
				++tail;
				que[tail][0]=i;
				que[tail][1]=j;
			}
	while (head<tail)
	{
		head++;
		x=que[head][0];
		y=que[head][1];
		for (d=0;d<4;d++)
		{
			a=x+Dir[d][0];
			b=y+Dir[d][1];
			if (a>=0 && a<=n && b>=0 && b<=m)//is in map
				if (visit[a][b]==0)
				{	
					visit[a][b]=1;
					dis[a][b]=dis[x][y]+1;
					//add to queue
					++tail;
					que[tail][0]=a;
					que[tail][1]=b;
				}
		}
	}
	
}

void run()
{
	bfs();
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			cout<<dis[i][j];
			if (j!=m-1)
				cout<<' ';
		}
		if (i!=n-1)
			cout<<endl;
	}
}

void ini()
{
	char c;
	cin>>n>>m;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			cin>>c;
			data[i][j]=c-'0';
		}
	for (int i=0;i<MAXN;i++)
		for (int j=0;j<MAXN;j++)
			dis[i][j]=INF;
}

int main()
{
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	ini();
	run();
	return 0;
}