posted on 2021-02-27 10:04:32 | under 题解 | source
这道题其实没有绿这么难，只需要二分+搜索就行了。
- 读入。注意尽量不要用
scanf读入bool，这好像是 UB，可以用一个变量 \(x\) 存输入的数，然后直接类型转换。 - 二分。套模版就行了，等一下我们再写 \(\operatorname{check}()\) 函数。
- 搜索。直接 dfs 爆搜，注意我们只需要标记这个点能不能到，不用回溯。
- \(\operatorname{check}()\)。我们先清空数组，然后随便挑一个点开始暴搜（实测 \(\operatorname{dfs}(1,1)\) 能过）。然后两重 for 循环暴力检查，如果发现一个关键点没被标记，说明这个解不合法，
return 0。如果到最后还没有return 0，说明这个解合法，return 1。
#include <cstdio>
#include <cstring>
using namespace std;
const int dx[]={0,-1,0,0,1},//四方向打表
dy[]={0,0,-1,1,0};
int n,m,a[510][510];
bool vis[510][510],key[510][510];//vis标记，key关键点
int abs(int a){//把一些常用函数封一下
return a<0?-a:a;
}
bool checkpoint(int x,int y){
return 1<=x&&x<=n&&1<=y&&y<=m;
}
void dfs(int x,int y,int nowans){//搜索
for(int i=1;i<=4;i++){
int tmpx=x+dx[i],tmpy=y+dy[i];
if(checkpoint(tmpx,tmpy)&&!vis[tmpx][tmpy]&&\
abs(a[x][y]-a[tmpx][tmpy])<=nowans){//这里\可以使上下两行无缝衔接，可以用这个减少一行的长度
vis[tmpx][tmpy]=1;
dfs(tmpx,tmpy,nowans);
//不用回溯
}
}
}
bool check(int nowans){//暴力check
memset(vis,0,sizeof vis);
vis[1][1]=1;//注意标记起点
dfs(1,1,nowans);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(key[i][j]&&!vis[i][j]) return 0;
return 1;
}
int binary(){//套模版
int l=0,r=1e9+10;
while(l<=r){
int mid=l+r>>1;//1e9+1e9=2e9不爆int
if(check(mid)) r=mid-1;
else l=mid+1;
}
return r+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1,x;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&x),key[i][j]=x;//防UB
printf("%d",binary());
return 0;
}