题解 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;
}

发表于 2020-06-13 19:11:13 in 题解