P2335 [SDOI2005]位图 题解

description：

题目描述

现在我们给出一个 $n\times m$ 的单色位图，且该图中至少含有一个白色的像素。我们用(i, j)来代表第i行第j列的像素，并且定义两点 $p_1=(i_1, j_1)$ 和 $p_2=(i_2, j_2)$ 之间的距离为：

$d(p_1, p_2)=|i_1 - i_2| + |j_1 – j_2|$

任务：

请写一个程序：

从文本文件 BIT.IN 中读入该位图；

对于每个像素，计算出离该像素最近的白色像素与它的距离；

把结果输出。

输入格式

第一行包括两个用空格分开的整数 $n$ 和 $m$，$1\le n\le 150$，$1\le m\le 150$。

以下的 $n$ 行每行包括一个长度为 $m$ 的整数为零或一，在第 $i+1$ 行的第 $j$ 个字符如果为 1，那么表示像素 $(i, j)$ 为白的，否则为黑的。

输出格式

输出一个 $n\times m$ 的数表，其中的第 $i$ 行的第 $j$ 个数字为 $f(i, j)$ 表示像素 $(i, j)$ 到最近的白色像素的距离。

solution：

观察到数据范围较小，那不妨直接找出所有的白点，然后依次更新到每个黑点的距离。如果距离比原来这个黑点的最佳距离更小，那么就更小它。

最劣时间复杂度：$O(n^4)$，然而一般远无法达到。

code：

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
queue<pair<int,int> >q;
int dis[155][155],a[155][155];
int abs(int x)
{
	if(x<0)return -x;
	return x;
}
int main()
{
	memset(dis,0x3f,sizeof(dis));
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			if(a[i][j]==1)
			{
				q.push(make_pair(i,j));
			}
		}
	}
	while(!q.empty())
	{
		int x=q.top().first;
		int y=q.top().second;
		q.pop();
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(a[i][j]==0)
				{
					dis[i][j]=min(dis[i][j],abs(i-x)+abs(j-y));
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]==1)
			{
				printf("0 ");
			}
			else
			{
				printf("%d ",dis[i][j]);
			}
		}
		printf("\n");
	}
	return 0;
}