题解思路

我们可以将山脉地图看成一个二维网格，每个格子代表一个节点，相邻（上、下、左、右）格子之间有边相连。由于每步移动代价相同（均为 1），并且我们要找从山底到山峰的最少步数，最合适的算法是 广度优先搜索（BFS）。

具体步骤如下：

1. 扫描地图，找到山底起点 start（高度为 0 的唯一坐标）和山峰终点 target（最高高度的唯一坐标）。
2. 初始化队列，将 start 入队，并用一个与地图同型的布尔数组 vis 记录访问状态。
3. BFS 过程：

题目内容

给定一个二维数组 $mountainMap$表示一座山的地图,数组中的每个元素 $mountainMap[x][y]$代表坐标$(x,y)$处山的高度。登山员从山底出发，爬到山峰。

山底的含义:$mountainMap$中高度为0的坐标点.

山峰的含义:$mountainMap$中高度最高的坐标点。

山底和山峰有且仅有一个坐标。

登山员每次移动只能从当前位置向上下左右四个方向移动一格,向高处移动时，移动到的位置的山的高度不能高于当前位置山的高度加上固定的攀爬能力值$climbAbility$；向低处移动时,移动到的位置的山的高度不能低于当前位置山的高度减去$climbAbility$。 数值取值范围:

请计算出从山底移动到山峰，最少需要移动几次?

输入描述

1.第一行为$climbAbility$的值

2.第二行为$mountainMapRows\ mountainMapCols$

3.从第三行开始为$mountainMapRows$行$mountainMapCols$列的高度

二维数组$mountainMap[mountainMapRows][mountainMapCols]$,

每行的高度数字中间用空格分割

样例输入

$1$

$6\ 6$

$4\ 5\ 6\ 5\ 5\ 5$

$3\ 4\ 5\ 6\ 7\ 7$

$2\ 10\ 10\ 10\ 8\ 8$

$1\ 1\ 1\ 10\ 9 \ 9$

$1\ 0\ 10\ 10\ 10\ 10$

$9\ 9\ 9\ 9\ 11\ 10$

图例：

格子中的数字代表山峰高度，$climbAbility$为$1$，最短路线如图所示。

输出描述

从山底移动到山峰，最少移动次数。

如果无法移动至山峰，则输出$-1$

样例1

输入

2
3 2
1 3
0 4
5 3

输出

5

说明

攀登能力为$2$，$3$行$2$列的山峰坐标，山底的坐标为$(1,0)$高度$0$，山峰的坐标为$(2,0)$高度$5$。

仅有一条路线 初始位置山底$(1,0)$高度$0->(0,0)$高度$1->(0,1)$高度$2$->$(1,1)$高度$4$->$(2,1)$高度$3->(2,0)$高度$5$

共需要移动$5$次。

样例2

输入

1 
4 5
1 1 1 1 1
1 0 1 2 1
1 1 1 3 1
1 1 1 1 1

输出

3

说明

攀登能力为$1$，$4$行$5$列的山峰坐标，山底的坐标为$(1,1)$，山峰的坐标为$(2,3)$。

最短路线为

初始位置山底$(1,1)$高度$0->(1,2)$高度$1->(1,3$)高度$2->$山峰$(2,3)$高度$3$

共需要移动$3$次

样例3

输入

1
4 5
1 1 1 1 1
1 0 1 2 1
1 1 1 9 1
1 1 1 1 1

输出

-1

说明

无法达到山峰，输出$-1$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写