题解 P4955 【[USACO14JAN]Cross Country Skiing S】

posted on 2021-02-27 10:04:32 | under 题解 | source

这道题其实没有绿这么难，只需要二分+搜索就行了。

1. 读入。注意尽量不要用 scanf 读入 bool，这好像是 UB，可以用一个变量 \(x\) 存输入的数，然后直接类型转换。
2. 二分。套模版就行了，等一下我们再写 \(\operatorname{check}()\) 函数。
3. 搜索。直接 dfs 爆搜，注意我们只需要标记这个点能不能到，不用回溯。
4. \(\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;
}