当前位置:网站首页>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 可以对难度二分的方法
也就是找到一个确定的难度,然后根据难度搜索,就能大大减少搜索的次数
如果我们能根据难度找到一条符合条件的路,那么就可以通过二分法继续缩小难度的范围来继续查找。直到找到最小。
边栏推荐
猜你喜欢
随机推荐
OSI网络模型
IP地址及子网划分
Object detection app based on appinventor and EasyDL object detection API
.net(四) 数据层实现
Process synchronization and mutual exclusion problem
Introduction to the Endpoint
三层交换机原理及配置
Operations in the database (syntax)
Non-decreasing Array
Routing configuration forwarding and experiment
pragma comment的使用(转载)重新排版
三次握手,四次挥手
[MySQL]mysql: Solve the problem of [Err] 1093 - You can't specify target table 'table name' for update in FROM clause
Processes and Scheduled Tasks
Redis redis 】 【 the expiration of listening
数据库中的操作(语法)
测试和开发之间的恩恩怨怨
继承中的运算符重载:输入输出的传奇
转换为onnx模型错误汇总
静态路由原理与配置








