最近总喜欢在SPOJ上刷黑白双煞题
这题的思路异常简单。实际上，如果你稍微看一看，就会发现……
所以很多人第一反应想到的就是暴力搜索啊！
- 只需要输入+搜索就可以搞定啊！
虽然我没试过，但是大概算一下，搞不好最坏要：T 组数据 · 矩阵大小 · 矩阵大小 （枚举0、1两格）
矩阵长和宽为182的范围感觉还是吃不消的。
所以就需要进一步优化。
其实具体也还是很简单的：
-
既然我们枚举的是0、1两格的位置……
-
具体记录也很简单，输入时加个 if-else 就可以了。如果怕空间浪费的话，可以用 STL 的 vector ，动态延长数组，在此基础上的访问和末尾添加元素也和数组一样是 O(1) 的。
回到正题，如果记录下来了每个0和1的位置，就只需要枚举位置就行了。大概可以优化到 O(T * n)。（T是数据组数）
最后乘上数据数量，虽然 T 的范围我没有找到，但实测得出这是不会TLE的。
或许就可以打出代码了……
#include<bits/stdc++.h>
using namespace std;
int T,n,m,i,j,b[190][190],s;
bool a[190][190];
char x;
vector<int> z[2];
vector<int> w[2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T-->0){
cin>>n>>m;
for(i=1;i<=n;i++) for(j=1;j<=m;j++){
cin>>x;
if(x=='0') a[i][j]=0;
else a[i][j]=1;
if(!a[i][j]){
z[0].push_back(i);
z[1].push_back(j);
}
else{
w[0].push_back(i);
w[1].push_back(j);
}
}
for(i=0;i<z[0].size();i++){
s=2147483647;
for(j=0;j<w[0].size();j++) s=min(s,abs(z[0][i]-w[0][j])+abs(z[1][i]-w[1][j]));
b[z[0][i]][z[1][i]]=s;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) cout<<b[i][j]<<" ";
cout<<"\n";
}
}
return 0;
}
但是这个代码一交，就会发现…………
这里大家一定要谨慎，因为多组数据的题目是要初始化的！
#include<bits/stdc++.h>
using namespace std;
int T,n,m,i,j,b[190][190],s;
bool a[190][190];
char x;
vector<int> z[2];
vector<int> w[2];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T-->0){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
z[0].clear();
z[1].clear();
w[0].clear();
w[1].clear();//初始化
cin>>n>>m;
for(i=1;i<=n;i++) for(j=1;j<=m;j++){
cin>>x;
if(x=='0') a[i][j]=0;
else a[i][j]=1;
if(!a[i][j]){
z[0].push_back(i);
z[1].push_back(j);
}
else{
w[0].push_back(i);
w[1].push_back(j);
}
}
for(i=0;i<z[0].size();i++){
s=2147483647;
for(j=0;j<w[0].size();j++) s=min(s,abs(z[0][i]-w[0][j])+abs(z[1][i]-w[1][j]));
b[z[0][i]][z[1][i]]=s;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) cout<<b[i][j]<<" ";
cout<<"\n";
}
}
return 0;
}
最终时间上优化差不多啦，现在看看有没有空间优化。
除了用 vector 以外，我们发现了一个无用的 a 数组。这个数组 ，可以去掉。
最终出现了这个
#include<bits/stdc++.h>
using namespace std;
int T,n,m,i,j,b[190][190],s;
//原先存矩阵的 a 数组被优化掉了
char x;
vector<int> z[2];
vector<int> w[2];
/*
* 第一维->横坐标
* 第二维->纵坐标
*/
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 以上是输入输出优化的代码
cin>>T;
while(T-->0){
memset(b,0,sizeof(b));
z[0].clear();
z[1].clear();
w[0].clear();
w[1].clear();
// ------初始化完毕-------- //
cin>>n>>m;
for(i=1;i<=n;i++) for(j=1;j<=m;j++){
cin>>x;
if(x=='0'){
z[0].push_back(i);
z[1].push_back(j);
}
else{
w[0].push_back(i);
w[1].push_back(j);
}
// 注意是字符串读入
}
for(i=0;i<z[0].size();i++){
s=2147483647;
// 这是int范围最大值
for(j=0;j<w[0].size();j++) s=min(s,abs(z[0][i]-w[0][j])+abs(z[1][i]-w[1][j])); // 这是题目里给出的坐标公式，注意取绝对值，不然有可能得到个负数
b[z[0][i]][z[1][i]]=s;
// 存储答案
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++) cout<<b[i][j]<<" ";
cout<<"\n";
}
// 以上是输出，不用讲吧~
}
return 0;
}
以上题解中出现的代码本蒟蒻都已经交过并测试了，这里是我的提交记录，已经加入代码公开计划了~
