解题思路
本题在 n×m 网格上统计从唯一全局最小值格子走到唯一全局最大值格子的路径条数。每一步只能走向四邻域中海拔严格更高的格子,且高度差不超过 maxDiff。路径上每个格子最多访问一次;由于海拔沿步严格递增,图中不存在环路,从任意格子沿合法边走向更高海拔构成有向无环图(DAG),因此可用 记忆化搜索(DFS + memo) 自终点(或自起点)统计路径数。
具体做法:
- 扫描网格得到全局最小值、最大值及其坐标 (sx,sy)、(tx,ty)(题面保证各唯一)。
- 定义
dfs(i,j):从 (i,j) 出发,沿「海拔上升且步长 ∈(0,maxDiff]」的四连通边走到终点的路径数。
- 边界:若 (i,j) 为终点,返回 1;否则对四个方向尝试扩展,累加合法邻居的
dfs 结果。
P4726.勇攀数字高峰(200分)
题目描述
你在给定的数字地形图中寻找登山路径,数字代表当前位置的海拔高度,要求从最低海拔出发,不断攀登,最终到达最高山峰。你需要寻找所有满足条件的登山路径。
地图已经保证最低海拔和最高山峰都只有一个。
路径条件
- 登山规则:路径上的海拔必须严格递增
- 移动限制:可以向上下左右 4 个方向移动
- 路径限制:路径必须从最低海拔开始,到最高海拔结束
- 访问控制:每个地点只能走一次
- 高度差限制:每一步的攀登高度差必须大于 0,小于等于指定值
输入格式
输入一个二维数组表示的海拔图,维度为 n×m(2≤n,m≤10),每个元素都是一个整数 x
输入一个整数参数表示单步最大允许的高度差
输出格式
输出满足条件的登山路径的数量
示例1
输入
[[1,2],[3,5]],2
输出
1
说明
起点:最低点坐标 (0,0),海拔高度 1
终点:最高点坐标 (1,1),海拔高度 5
单步最大高度差:2
可行路径:
路径 1:(0,0),(1,0),(1,1)
示例2
输入
[[4,3],[3,2]],1
输出
2
说明
起点:最低点坐标 (1,1),海拔高度 2
终点:最高点坐标 (0,0),海拔高度 4
单步最大高度差:1
可行路径:
路径 1:(1,1),(0,1),(0,0)
路径 2:(1,1),(1,0),(0,0)
示例3
输入
[[1,3],[3,4]],1
输出
0
说明
起点:最低点坐标 (0,0),海拔高度 1
终点:最高点坐标 (1,1),海拔高度 4
单步最大高度差:1
可行路径:0