记录编号	478010	评测结果	AAAAAAAAAAAAAAAA
题目名称	[POI 1999] 位图	最终得分	100
用户昵称	HtBest	是否通过	通过
代码语言	C++	运行时间	2.598 s
提交时间	2017-12-08 00:11:46	内存使用	0.55 MiB

#define _CRT_SECURE_NO_DEPRECATE
/************************
*创建时间：2017 12 07
*文件类型：源代码文件
*题目来源：COGS
*采用算法：BFS
*作者：HtBest
************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
struct dot
{
	int x, y, w;
	dot(int a = 0, int b = 0, int c = 0)
	{
		x = a;
		y = b;
		w = c;
	}
}now;
std::queue <dot> bfss;
char a[200][200];
int n, m, move[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } }, b[200][200] = { 0 };
bool use[200][200] = { 0 };
void read()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
	{
		scanf("%s", a[i]);
	}
	return;
}
int bfs()
{
	for (int i = 0; !bfss.empty(); ++i)
	{
		now = bfss.front();
		bfss.pop();
		for (int j = 0; j < 4; ++j)
			if (now.x + move[j][0] >= 0 && now.x + move[j][0]<n && now.y + move[j][1] >= 0 && now.y + move[j][1]<m && !use[now.x + move[j][0]][now.y + move[j][1]]&&a[now.x+move[j][0]][now.y+move[j][1]]=='0')
			{
				use[now.x + move[j][0]][now.y + move[j][1]] = true;
				int *t = &b[now.x + move[j][0]][now.y + move[j][1]];
				if (*t == 0)	*t = now.w + 1;
				*t = std::min(*t, now.w + 1);
				bfss.push(dot(now.x + move[j][0], now.y + move[j][1], now.w + 1));
			}
	}
	return 0;
}
int main()
{
	freopen("bit.in", "r", stdin);
	freopen("bit.out", "w", stdout);
	read();
	for (int i = 0; i<n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (a[i][j]=='1')
			{
				while (bfss.size())	bfss.pop();
				memset(use, 0, sizeof(use));
				use[i][j] = true;
				bfss.push(dot(i, j, 0));
				bfs();
			}
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			printf("%d ", b[i][j]);
		puts("");
	}

	return 0;
}