解题思路
本题在 n×m 网格上统计从唯一全局最小值格子走到唯一全局最大值格子的路径条数。每一步只能走向四邻域中海拔严格更高的格子,且高度差不超过 maxDiff。路径上每个格子最多访问一次;由于海拔沿步严格递增,图中不存在环路,从任意格子沿合法边走向更高海拔构成有向无环图(DAG),因此可用 记忆化搜索(DFS + memo) 自终点(或自起点)统计路径数。
具体做法:
- 扫描网格得到全局最小值、最大值及其坐标 (sx,sy)、(tx,ty)(题面保证各唯一)。
- 定义
dfs(i,j):从 (i,j) 出发,沿「海拔上升且步长 ∈(0,maxDiff]」的四连通边走到终点的路径数。
- 边界:若 (i,j) 为终点,返回 1;否则对四个方向尝试扩展,累加合法邻居的
dfs 结果。