【POI1999】位图——洛谷P2335

现在我们给出一个n*m的单色位图，且该图中至少含有一个白色的像素。我们用(i, j)来代表第i行第j列的像素，并且定义两点p1=(i1, j1)和p2=(i2, j2)之间的距离为：

d(p1, p2)=|i1 - i2| + |j1 – j2| 

任务：

请写一个程序：

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

把结果输出。

输入输出格式

第一行包括两个用空格分开的整数n和m，1<=n<=182，1<=m<=182。

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

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

输入输出样例

3 4
0 0 0 1
0 0 1 1
0 1 1 0

输出样例： 

3 2 1 0
2 1 0 0
1 0 0 1

题目分析：

读题后不难想到：对于每一个黑色像素，都去进行一次广度优先搜索，找到最近的白色像素。对于每一个白色像素，最近的白色像素就是自己。但是n，m的范围过大，超时！

故此题采用：多源最短路算法

对每一个白点进行广度优先搜索，由它去更新黑点的答案，再由已经更新的黑点去更新其他黑点的答案，但每个点不是只去一次，当我们发现存在更优解时应当重新加入队列进行更新.对每一个白点进行广度优先搜索，由它去更新黑点的答案，再由已经更新的黑点去更新其他黑点的答案，但每个黑点不是只更新一次，当我们发现存在更优解时应当重新加入队列进行更新.

代码如下：

#include
using namespace std;
struct _
{
	int x,y;
}q[182*182+5];//存白像素点
int ans[183][183],n,m,cnt;//ans为答案数组，cnt为有多少个白点 
bool flag[183][183];//false代表黑点，true代表白点 
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};//方向数组，搜四周的点 
void BFS()
{
	int h=1,t=cnt,nx,ny,i;
	while(h<=t)//BFS模板 
	{
		for(i=0;i<=3;i++)
		{
			nx=q[h].x+dx[i];
			ny=q[h].y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m)//首先不能越界 
			{
				if(!flag[nx][ny]&&ans[q[h].x][q[h].y]+1>ch;
			if(ch=='0')flag[i][j]=false,ans[i][j]=0x7ff;//黑点为false，ans定大方便之后更新答案 
			else//把所有的白点丢进队列 
			{
				cnt++;
				q[cnt].x=i;q[cnt].y=j;
				flag[i][j]=true;
				ans[i][j]=0; 
			}
		}
	}
	BFS();//利用所有的白点去搜索，只需一次搜索即可 
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}