题解 | #D 迷阵#

二分搜索答案。
代码里面有注释。

#include<bits/stdc++.h>
using namespace std;
int dir[4][2]= {{1, 0}, {0, 1}, {0, -1},{-1, 0}};
int n;
int vis[110][110], a[110][110];

// 防止越界、或者重复访问 
bool check(int x, int y){
    if(x < 1 || x > n){
        return false;
    }
    if(y < 1 || y > n){
        return false;
    }
    if(vis[x][y]){
        return false;
    }

    return true;
}

void dfs(int x, int y, int minn, int maxn){
    // 四个方向硬搜 
    for(int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];

        // 搜索的值都在minn 和 maxn之内 
        if(check(xx,yy) && a[xx][yy] >= minn && a[xx][yy] <= maxn) {
            vis[xx][yy] = 1;
            dfs(xx, yy, minn, maxn);
        }
    }
}



int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin>>a[i][j];
        }
    }
    // 二分遍历答案 
    int l = 0, r = 3000, res = 3000;
    while(l <= r){
        int mid = (l + r) >> 1;
        int f = 0;
        // 遍历minn 和 maxn
        // maxn - minn = mid
        for(int i = 0; i < 3000 - mid; i++){
            if(a[1][1] < i || a[1][1] > i + mid)    continue;
            memset(vis, 0, sizeof(vis));
            vis[1][1] = 1;
            // 起始点, 最小值, 最大值 
            dfs(1, 1, i, i + mid);

            // 如果能够到达终点 
            if(vis[n][n]){
                f = 1;
                break;
            }
        }
        if(f){
            res = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;

        }
    }

    cout<<res;


    return 0;
}