题目内容

给定一个二维数组 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 1 2 2 2
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)高度3 -> (1,1)高度4 -> (2,1)高度3 -> (2,0)高度5

共需要移动5次

样例2

输入

1
4 5
1 1 1 1 1
1 1 1 1 1
1 0 1 2 1
1 1 1 9 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 1 1 1 1
1 0 1 2 1
1 1 1 9 1
1 1 1 1 1

输出

-1

说明

无法达到山峰，输出 -1

提示

1. 山底和山峰有且仅有一个坐标。
2. 初始位置在山底，山底不一定在数组边缘位置，见样例2
3. 山峰的高度大于0