题目名称

远足登山

题目描述

在风景如画的山区，有一位经验丰富的登山老师 L 老师，正带领一群学生进行一次具有挑战性的登山远足。他们身处一个由 $n$ 行 $m$ 列组成的地图中，地图上的每个格子都标记了相应的海拔高度。

L 老师和学生们的起点是地图的最左上角，目标是到达地图的最右下角。每个格子代表着一处不同的山地地形。

作为登山老师，L 老师希望为学生们规划一条体力消耗最小的路线，以确保他们能够安全、顺利地登上山顶。

路线的体力消耗定义为：路线上相邻格子之间海拔高度差的最大值。

你的任务是帮助 L 老师计算从起点到终点的最小体力消耗值，以协助他们成功完成这次登山远足。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示地图格子的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，这些整数表示对应格子的海拔高度值（即体力消耗参考值 ）。

输出格式

输出从地图左上角走到右下角的最小体力消耗值。

样例数据

样例 1 输入：

3 3
1 2 2
3 8 2
5 3 5

输出：

2

样例 2 输入：

3 3
1 2 3
3 8 4
5 3 5

输出：

1

样例 3 输入：

5 5
1 2 1 1 1
1 2 1 2 1
1 2 1 2 1
1 2 1 2 1
1 1 1 2 1

输出：

0

样例解释

• 样例 1 解释：对于路径 1,3,5,3,5 ，连续格子的高度差值绝对值最大为 2 。此路径比路径 1,2,2,2,5 更优，因为后者路径的高度差值最大值为 3 。
• 样例 2 解释：对于路径 1,2,3,4,5 ，相邻格子的高度差值绝对值最大为 1 ，比路径 1,3,5,3,5 更优。
• 样例 3 解释：上述路径不需要消耗任何体力，因此输出 0 。

数据范围

• 对于 30%的数据：$1 \leq n \leq 10$，$1 \leq m \leq 10$，$1 \leq a[i][j] \leq 10^{2}$ 。
• 对于 60%的数据：$1 \leq n \leq 10^{2}$，$1 \leq m \leq 10^{2}$，$1 \leq a[i][j] \leq 10^{4}$ 。
• 对于 100%的数据：$1 \leq n \leq 10^{3}$，$1 \leq m \leq 10^{3}$，$1 \leq a[i][j] \leq 10^{6}$ 。