题解 P1256 【显示图像】
Callous_Murder
·
·
题解
这题真的坑，虽然我一遍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
由此得出：
好啦，那我们开始暴力吧！
```cpp
#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了……
（写得算详细，喜欢就给个赞吧~