当前位置:网站首页>nyoj306 走迷宫(搜索+二分)
nyoj306 走迷宫(搜索+二分)
2022-08-09 08:10:00 【51CTO】
走迷宫
1000 ms | 内存限制: 65535
Dr.Kong设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲。这天卡多又跑出来了,在SJTL游乐场玩个不停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫。 整 个迷宫是 用一个N * N的方阵给出 , 方阵中 单元格中 填充了一 个 整数 ,表示走到这个位置的难度。
这个迷宫可以向上走,向下走,向右走,向左走,但是不能穿越对角线。走迷宫的取胜规则很有意思,看谁能更快地找到一条路径,其路径上单元格最大难度值与最小难度值之差是最小的。当然了,或许这样的路径不是最短路径。
机器人卡多现在在迷宫的左上角(第一行,第一列)而出口在迷宫的右下角(第N行,第N列)。
卡多很聪明,很快就找到了这样的一条路径。你能找到吗?
有多组测试数据,以EOF为输入结束的标志
第一行: N 表示迷宫是N*N方阵 (2≤ N≤ 100)
接下来有N行, 每一行包含N个整数,用来表示每个单元格中难度 (0≤任意难度≤120)。
输出 输出为一个整数,表示路径上最高难度与和最低难度的差。 样例输入
样例输出
2
来源 第四届河南省程序设计大赛
上传者 张云聪
这种思路的确是没想到
由于这道题的难度范围是0-120 可以对难度二分的方法
也就是找到一个确定的难度,然后根据难度搜索,就能大大减少搜索的次数
如果我们能根据难度找到一条符合条件的路,那么就可以通过二分法继续缩小难度的范围来继续查找。直到找到最小。
边栏推荐
- Talking about Flask_script
- Notes on OpenHarmony Open Source Meeting (Nanjing Station)
- Introduction to the Endpoint
- Object detection app based on appinventor and EasyDL object detection API
- 正则之re模块
- 3D软件开发工具HOOPS全套产品开发介绍 | HOOPS Exchange、HOOPS Communicator
- 数制转换及子网划分
- jdbctemplate连接sql server,代码中查出来的数据跟数据库中不一致,如何解决?
- IP地址及子网划分
- 梅科尔工作室--BP神经网络培训笔记
猜你喜欢
网络布线及数制转换
[MySQL]mysql: Solve the problem of [Err] 1093 - You can't specify target table 'table name' for update in FROM clause
Conversion between number systems
System Security and Application
P1064 Jin Ming's Budget Plan
scp上传文件到远程服务器
消息中间件(MQ)前置知识介绍(必看)
IO byte stream reads text Chinese garbled
Introduction to Network Layer Protocols
OSI网络模型
随机推荐
pip3 source change to improve speed
Non-decreasing Array
6000 字+,帮你搞懂互联网架构演变历程!
SOLIDWORKS Simulation教程:计算物体的固有频率
文件处理(IO)
火星人 --简单的数学题
鸿蒙开发实战一——手表篇
Cookie and Session Details
File Handling (IO)
可能导致Loadrunner检查点中savecount为0的分析
Web 3D渲染引擎HOOPS Communicator动画编辑器的使用 | HOOPS教程
账户和权限管理2
Redis redis 】 【 the expiration of listening
转换为onnx模型错误汇总
OpenHarmony轻智能产品开发直播笔记
Introduction to Network Layer Protocols
数制转换及子网划分
3安装及管理程序
Database MySQL installation and uninstallation
The MySQL database