解题思路

这道题本质上是一个 DFS + 回溯 的搜索问题。

题目要求：

• 必须从全图唯一的最低点出发；
• 到达全图唯一的最高点结束；
• 每一步只能往上下左右 $4$ 个方向走；

题目描述

你在给定的数字地形图中寻找登山路径，数字代表当前位置的海拔高度，要求从最低海拔出发，不断攀登，最终到达最高山峰。你需要寻找所有满足条件的登山路径。 地图已经保证最低海拔和最高山峰都只有一个。

路径条件

• 登山规则：路径上的海拔必须严格递增
• 移动限制：可以向上下左右 $4$ 个方向移动
• 路径限制：路径必须从最低海拔开始，到最高海拔结束
• 访问控制：每个地点只能走一次
• 高度差限制：每一步的攀登高度差必须大于 $0$，小于等于指定值

输入格式

输入一个二维数组表示的海拔图，维度为 $n \times m$（$2 \le n,m \le 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$