自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:22:59，当前版本为作者最后更新于2020-02-07 14:18:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题真的坑，虽然我一遍AC了

题解区兜了一圈，好像都是写搜索的。。

呦呵，这不是暴力吗？？

---

原题链接

题面我看了好几遍才看懂（出题人能不能直截了当一点啊），其实就是一句话：

每个像素点和其最近的显示白色的像素点之间的最短距离是多少。

---

只要分两种情况考虑：

1.$a_{i,j}$为$1$，也就是当前像素点为白像素点。

这简单，里$a{i,j}$最近的白像素点不就是自己吗？

所以，最短距离为$0$。

2.$a_{i,j}$为$0$，也就是当前像素点为黑像素点。

暴力就是在这里，去寻找白像素点，求出最短距离。

---

考虑清楚了，那就想一想怎么暴力吧。

要是双重循环枚举每个像素点然后进行处理那肯定是不行的，复杂度太高了，会TLE的。

我想到的是：

用$b$数组存储当前像素点的信息，用$a$数组存储当前像素点与白色像素点之间的最短距离。

双重循环。

如果$b_{i,j}=true$，是白像素点，$a_{i,j}=0$，双重循环，将每个黑像素点和当前白像素点的距离计算出来，然后跟先前的数作比较，比Ta小，就替换。

注意，$a$数组的初始值要很大。

• 如何计算两个像素点之间的距离

观察一下这张图，两点之间的最短路径和什么有关呢？

图$1$：

最短路径为$3$。

$abs($橙圈所在行$-$绿圈所在行$)+abs($橙圈所在列$-$绿圈所在列$=(2-1)+(4-2)=1+2=3$

图$2$：

最短路径为$2$。

$abs($橙圈所在行$-$绿圈所在行$)+abs($橙圈所在列$-$绿圈所在列$=(4-3)+(3-2)=1+1=2$

图$3$：

最短路径为$5$。

$abs($橙圈所在行$-$绿圈所在行$)+abs($橙圈所在列$-$绿圈所在列$=(4-2)+(4-1)=2+3=5$

发现什么了吗？

验证一下。

图$4$：

最短路径为$5$。

$abs($橙圈所在行$-$绿圈所在行$)+abs($橙圈所在列$-$绿圈所在列$=(4-1)+(3-1)=3+2=5$

由此得出：

$a_{i,j}$和$a_{k,t}$的最短路径为，$abs(i-k)+abs(j-t)$。

好啦，那我们开始暴力吧！

#include<bits/stdc++.h>
using namespace std;
int n,m,a[183][183],d;
bool b[183][183];
char s[183];
void f(int x,int y) {
    int i=1;
    while(i<=n) {
        for(int j=1; j<=m; ++j) {
            if(b[i][j]==true) continue;
            d=abs(x-i)+abs(y-j);
            a[i][j]=min(a[i][j],d);
        }
        ++i;
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) 
        for(int j=1; j<=m; ++j) {
        	scanf("%d",&b[i][j]);
            if(b[i][j+1]==true) a[i][j+1]=0;
            else a[i][j+1]=1e9;
        }
    for(int x=1; x<=n; ++x)
        for(int y=1; y<=m; ++y) {
            if(b[x][y]) {
                int k=1;
                while(k<=n) {
                    for(int j=1; j<=m; ++j) {
                        if(b[k][j]==true) continue;
                        d=abs(x-k)+abs(y-j);
                        a[k][j]=min(a[k][j],d);
                    }
                    ++k;
                }
            }
        }
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

我谔谔，为什么输入怪怪的啊~

然后，就发现了一个巨坑无比的东西，输入！

这是样例：

$in$

3 4
0001
0011
0110

$out$

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

您仔细看，有什么不同？？

恍然大悟，输入的矩阵中数字之间没有空格！！

（我差点气得吐血，我可是调了一上午啊

这样，就得用字符串读入：

for(int i=1; i<=n; ++i) {
    scanf("%s",s);
    for(int j=0; j<m; ++j) {
        b[i][j+1]=s[j]-'0';
        if(b[i][j+1]==true) a[i][j+1]=0;
        else a[i][j+1]=1e9;
    }
}

就这样，意料之中地AC了……

（写得算详细，喜欢就给个赞吧~