NYOJ306走迷宫(dfs+二分搜索)

作者：拍友2502878393 | 来源：互联网 | 2023-10-16 16:57

题目描述http:acm.nyist.netJudgeOnlineproblem.php?pid306Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场

题目描述
http://acm.nyist.net/JudgeOnline/problem.php?pid=306
Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。

这个迷宫可以向上走，向下走，向右走，向左走，但是不能穿越对角线。走迷宫的取胜规则很有意思，看谁能更快地找到一条路径，其路径上单元格最大难度值与最小难度值之差是最小的。当然了，或许这样的路径不是最短路径。

     机器人卡多现在在迷宫的左上角（第一行，第一列）而出口在迷宫的右下角（第N行，第N列）。

卡多很聪明，很快就找到了这样的一条路径。你能找到吗？

输入
有多组测试数据，以EOF为输入结束的标志
第一行： N 表示迷宫是N*N方阵 (2≤ N≤ 100)
接下来有N行，每一行包含N个整数，用来表示每个单元格中难度 (0≤任意难度≤120)。
输出
输出为一个整数，表示路径上最高难度与和最低难度的差。
样例输入

样例输出

题目分析：
对于每一个答案的范围，dfs判断对于当前范围值是否能否从(1,1)到达(n,n)。如果能找到某一路径到达(n,n)，则证明当前答案能够满足要求，还可以继续减小。我们可以二分[0,max-min]之间的值，进行判断即可。

AC代码：

/** *@xiaoran *dfs+二分搜索 *迷宫可以向上走，向下走，向右走，向左走 *从(1,1)到(n,n)能否找到一条路径， *其路径上单元格最大难度值与最小难度值之差是最小的 */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
/** *minn：地图中的最小值， *maxn：地图中的最大值， *flag：标记差值在某个范围内是否能够到达(n,n) *vmap[][]：地图 *vis[i][j]：该节点是否已被访问 *dx[],dy[]:搜索四个方向 */
int n,minn,maxn,flag;
int vis[120][120],vmap[120][120];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

void Init(){
    minn=121;
    maxn=-1;
    memset(vmap,-1,sizeof(vmap));//这里一定要赋值为小于0或者大于120的值
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&vmap[i][j]);
            maxn=max(vmap[i][j],maxn);
            minn=min(vmap[i][j],minn);
        }
    }
}

/** *差值在R-L的范围内是否存在从(1,1)-->(n,n)的路径 *这里判断的是每一值是否在[L,R]之间· */
void dfs(int i,int j,int L,int R){
    if(flag) return;
    if(i==n&&j==n){//能够找到有效路径,返回，不在搜素其他值
        flag=1; return;
    }
    for(int k=0;k<4;k++){
        int xi=i+dx[k];
        int xj=j+dy[k];
        if(vmap[xi][xj]>=L&&vmap[xi][xj]<=R&&vis[xi][xj]==0){
            //改点的值满足条件且未被访问。
            vis[xi][xj]=1;//这里一定要先标记啊
            dfs(xi,xj,L,R);
        }

    }
}

/** *用来判断当差值为k时，是否满足能够找到从(1,1)-->(n,n)的路径 */
int Judge(int k){
    for(int i=minn;i<=maxn-k;i++){
        flag=0;//先标记没有合法路径
        //因为dfs函数中没有判断vmap[1][1]和vmap[n][n]是否合法，这里要特判
        if(vmap[1][1]1][1]>i+k) continue;
        if(vmap[n][n]i+k) continue;


        memset(vis,0,sizeof(vis));
        vis[1][1]=1;//从(1,1)访问
        dfs(1,1,i,i+k);
        if(flag) return 1;//可以找到有效路径从(1,1)-->(n,n)
    }
    return 0;
}

int Get_ans(){
    int l=0,r=maxn-minn;
    while(lint mid=(l+r)/2;
        if(Judge(mid)){//当前值mid合法，还可以继续减小搜素
            r=mid;
        }
        else l=mid+1;
    }
    return r;//return l;
}


int main()
{
    while(~scanf("%d",&n)){
        Init();
        printf("%d\n",Get_ans());
    }
    return 0;
}

推荐阅读

less
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
less
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
function
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
list
C#学习教程：在Console中工作但在Windows窗体中不工作的异步代码分享

本文分享了一个关于在C#中使用异步代码的问题，作者在控制台中运行时代码正常工作，但在Windows窗体中却无法正常工作。作者尝试搜索局域网上的主机，但在窗体中计数器没有减少。文章提供了相关的代码和解决思路。 ... [详细]

蜡笔小新 2023-12-14 15:56:00
input
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
js
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
list
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
char
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
char
JVM 学习总结（三）——对象存活判定算法的两种实现

本文介绍了垃圾收集器在回收堆内存前确定对象存活的两种算法：引用计数算法和可达性分析算法。引用计数算法通过计数器判定对象是否存活，虽然简单高效，但无法解决循环引用的问题；可达性分析算法通过判断对象是否可达来确定存活对象，是主流的Java虚拟机内存管理算法。 ... [详细]

蜡笔小新 2023-12-13 18:59:46
char
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
list
Golang如何使用Cookie跟踪位置

关键词：Golang, Cookie, 跟踪位置, net/http/cookiejar, package main, golang.org/x/net/publicsuffix, io/ioutil, log, net/http, net/http/cookiejar ... [详细]

蜡笔小新 2023-12-13 15:47:22
input
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
input
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
input
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
list
开发笔记：实验7的文件读写操作

本文介绍了使用C++的ofstream和ifstream类进行文件读写操作的方法，包括创建文件、写入文件和读取文件的过程。同时还介绍了如何判断文件是否成功打开和关闭文件的方法。通过本文的学习，读者可以了解如何在C++中进行文件读写操作。 ... [详细]

蜡笔小新 2023-12-12 17:48:18

拍友2502878393

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章