Beyond the Void
BYVoid
POI 1999 位图 Bitmap

简单的广搜题,从每个白像素开始向外广搜,如果新的路径距离比原来的距离小,更新原来的距离。

/* 
 * Problem: POI1999 bit
 * Author: Guo Jiabao
 * Time: 2008.12.10 16:13:20
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAX=183;
const int INF=0x7FFFFFFF;
const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};

struct point
{
	int x,y;
};

int N,M,Head,Tail;
int dist[MAX][MAX],bit[MAX][MAX];
point Que[MAX*MAX];

void init()
{
	int i,j,c;
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	scanf("%d%d",&N,&M);
	Head=0;Tail=-1;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=M;j++)
		{
			dist[i][j]=INF;
			c=getchar();
			while (c==10 || c==13) c=getchar();
			bit[i][j]=c-'0';
			if (c=='1')
			{
				Que[++Tail].x=i;
				Que[Tail].y=j;
				dist[i][j]=0;
			}
		}
	}
}

void BFS()
{
	point i,j;
	int k;
	while (Head<=Tail)
	{
		i=Que[Head++];
		for (k=0;k<4;k++)
		{
			j.x=i.x+dx[k]; j.y=i.y+dy[k];
			if (1<=j.x && j.x <=N && 1<=j.y && j.y<=M && dist[i.x][i.y]+1<dist[j.x][j.y])
			{
				dist[j.x][j.y]=dist[i.x][i.y]+1;
				Que[++Tail]=j;
			}
		}
	}
}

void print()
{
	int i,j;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=M;j++)
			printf("%d ",dist[i][j]);
		putchar('n');
	}
}

int main()
{
	init();
	BFS();
	print();
	return 0;
}
<h2><span class="mw-headline">位图</span></h2>

【问题描述 】

给定一个 n*m 的矩形位图,位图中的每个像素不是白色就是黑色,但至少有一个是白色的。第 i 行、第 j 列的像素被称作像素 (i, j) 。两个像素 p1 = (i1, j1) , p2 = (i2, j2) 之间的距离定义为: d(p1, p2) = |i1 - i2| + |j1 - j2|.

【 任务 】

编一个程序完成以下操作:
<ol>
	<li>从输入文件中读入此位图的有关信息。</li>
</ol>
<ol>
	<li>对于每个像素,计算此像素与离其最近的“白像素”的距离。</li>
</ol>
<ol>
	<li>将结果写到输出文件里面。</li>
</ol>
【输入格式 】

输入文件的第一行包含两个整数 n, m ( 1 ≤ n ≤ 182, 1 ≤ m ≤ 182 ),用一个空格隔开。接下来 n 行,每一行都包含一个长度为 m 的 01 串;第 i+1 行,第 j 列的字符若为 1 ,则像素 (i, j) 是白色的;否则是黑色的。

【输出格式 】

输出文件包含 n 行 , 每行有 m 个用空格隔开的整数。第 i 行、第 j 列的整数表示 (i, j) 与离它最近的白像素之间的距离

【样例输入】
<pre>3 4
0001
0011
0110</pre>
【样例输出】
<pre>3 2 1 0
2 1 0 0
1 0 0 1</pre>

上次修改时间 2017-02-03

相关日志