题解 | #D 迷阵#

字符串修改

https://ac.nowcoder.com/acm/contest/11232/A

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

#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;
}
全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
无能的丈夫:但我觉得这个hr语气没什么问题啊(没有恶意
点赞 评论 收藏
分享
强大的马里奥:不太可能,我校计算机硕士就业率99%
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务