题解 P2335 【[SDOI2005]位图】
ShineEternal
2020-06-13 19:11:13
[更佳的阅读效果。](https://vipblog.github.io/PzZ3xYQBd/)
## 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:
```cpp
#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;
}
```