题解 P2335 【[SDOI2005]位图】

ShineEternal

2020-06-13 19:11:13

Solution

[更佳的阅读效果。](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; } ```