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;
}

推荐阅读

php
云计算的优势与应用场景

本文详细探讨了云计算为企业和个人带来的多种优势，包括成本节约、安全性提升、灵活性增强等。同时介绍了云计算的五大核心特点，并结合实际案例进行分析。 ... [详细]

蜡笔小新 2024-12-23 13:54:13
php
紫荆花之恋：动态树上的小精灵友谊问题

本题来自WC2014，题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系，要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]

蜡笔小新 2024-12-22 14:36:54
php
解决Selenium浏览器实例化位置导致的闪退问题

本文探讨了在使用Selenium进行自动化测试时，由于webdriver对象实例化位置不同而导致浏览器闪退的问题，并提供了详细的代码示例和解决方案。 ... [详细]

蜡笔小新 2024-12-23 16:09:49
go
在Xcode中配置自定义文本样式

本文探讨了如何在iOS开发环境中，特别是在Xcode 6.1中，设置和应用自定义文本样式。我们将详细介绍实现方法，并提供一些实用的技巧。 ... [详细]

蜡笔小新 2024-12-23 14:36:31
php
C++ 中的链表实现与应用

本文介绍如何在 C++ 中使用链表结构存储和管理数据。通过具体示例，展示了静态链表的基本操作，包括节点的创建、链接及遍历。 ... [详细]

蜡笔小新 2024-12-23 14:22:40
php
递推算法与大数处理

本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数，并使用递推算法和大数处理技术来解决这一问题。 ... [详细]

蜡笔小新 2024-12-23 12:18:55
php
深入理解Lucene搜索机制

本文旨在帮助读者全面掌握Lucene搜索的编写步骤、核心API及其应用。通过详细解析Lucene的基本查询和查询解析器的使用方法，结合架构图和代码示例，带领读者深入了解Lucene搜索的工作流程。 ... [详细]

蜡笔小新 2024-12-23 11:06:10
go
丽江客栈选择问题

本文介绍了一道经典的算法题，题目涉及在丽江河边的n家特色客栈中选择住宿方案。两位游客希望住在色调相同的两家客栈，并在晚上选择一家最低消费不超过p元的咖啡店小聚。我们将详细探讨如何计算满足条件的住宿方案总数。 ... [详细]

蜡笔小新 2024-12-22 20:15:25
go
JSOI2010 蔬菜庆典：树结构中的无限大权值问题

本文探讨了 JSOI2010 的蔬菜庆典问题，主要关注如何处理非根非叶子节点的无限大权值情况。通过分析根节点及其子树的特性，提出了有效的解决方案，并详细解释了算法的实现过程。 ... [详细]

蜡笔小新 2024-12-22 18:57:48
php
哈密顿回路检测问题【25分】

哈密顿回路问题旨在寻找一个简单回路，该回路包含图中的每个顶点。本文将介绍如何判断给定的路径是否构成哈密顿回路。 ... [详细]

蜡笔小新 2024-12-23 21:02:53
php
Appium + Java 自动化测试中处理页面空白区域点击问题

在进行移动应用自动化测试时，有时会遇到某些页面没有返回按钮，只能通过点击空白区域返回的情况。本文将探讨如何在Appium + Java环境中有效解决此类问题，并提供详细的解决方案。 ... [详细]

蜡笔小新 2024-12-22 17:30:25
byte
优化DB2数据库性能的关键策略

本文详细介绍了优化DB2数据库性能的多种方法，涵盖统计信息更新、缓冲池调整、日志缓冲区配置、应用程序堆大小设置、排序堆参数调整、代理程序管理、锁机制优化、活动应用程序限制、页清除程序配置、I/O服务器数量设定以及编入组提交数调整等方面。通过这些技术手段，可以显著提升数据库的运行效率和响应速度。 ... [详细]

蜡笔小新 2024-12-22 16:20:33
byte
使用栈实现字符串中括号匹配的C++程序

本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现，并详细解释了算法的核心思想和具体实现步骤。 ... [详细]

蜡笔小新 2024-12-22 11:44:35
byte
深入解析GCD：任务队列与多线程编程

本文详细介绍了Grand Central Dispatch (GCD) 的核心概念和使用方法，探讨了任务队列、同步与异步执行以及常见的死锁问题。通过具体示例和代码片段，帮助开发者更好地理解和应用GCD进行多线程开发。 ... [详细]

蜡笔小新 2024-12-22 10:11:08
python
字符串中特定字符的移除方法

本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符，并提供了多种编程语言的实现示例。 ... [详细]

蜡笔小新 2024-12-22 00:08:06

拍友2502878393

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

Tags | 热门标签

RankList | 热门文章