- 描述
-
维恩是一个恐高的孩子，有一天他来到了一个新开的游乐园。这个游乐园有一个人气特别高的项目"错乱空间"，其中第一关是在一个房间内。玩家进入房间后，将面临若干个高低不一的平台，玩家需要在平台间上下跳跃来进行移动，最终到达终点，去往下一关。
我们可以将这个房间抽象为一张 n*m 的二维地图 G，其中 G[i][j] 表示平台 (i, j) 的高度。玩家进入房间后在最左上角的平台 (0, 0) 上，终点在最右下角的平台 (n-1, m-1) 上，每次可以向 上、下、左、右 四个方向之一移动。
对于任一连续路径，我们把路径中的任意相邻两个平台的高度差（指差的绝对值）的最大值叫做“最高差”。由于维恩恐高，所以他希望找到这样一条路径，该路径连通起点 (0,0) 到终点 (n-1,m-1)，并且该路径的“最高差”是所有连通起点和终点的路径中最小的。我们把满足这样条件的路径叫做“最优路径”。
请你帮维恩求出最优路径的最高差。（注意，最优路径可能不止一条，但所有最优路径的最高差肯定是唯一的。）
- 输入
- 第一行为两个整数 n, m (1<=n,m<=200)，表示房间的大小为 n*m。
接下来的 n 行，每行 m 个正整数，表示平台的高度 (1<=G[i][j]<=108)，每个数之间用空格分开。 - 输出
- 一个整数，表示最优路径的最高差
- 样例输入
-
样例输入1 3 3 1 2 2 3 8 2 5 3 5 样例输入2 3 3 5 4 6 4 1 4 3 4 5 样例输入3 5 7 1 2 1 1 1 1 1 1 2 1 2 2 2 1 1 2 1 2 1 1 1 1 2 1 2 1 2 2 1 1 1 2 1 1 1
- 样例输出
-
样例输出1 2 样例输出2 1 样例输出3 0
- 提示
- 样例 1 说明：
最优路径 1 -> 3 -> 5 -> 3 -> 5，最高差为 5 - 3 = 2，其余路径的最高差均大于 2
其余路径，例如 1 -> 2 -> 8 -> 2 -> 5 这条路径中的最高差为 8 - 2 = 6
1 -> 2 -> 2 -> 2 -> 5 这条路径中的最高差为 5 - 2 = 3
样例 2 说明：
最优路径 5 -> 4 -> 3 -> 4 -> 5，最高差为 1
其余路径，例如 5 -> 4 -> 1 -> 4 -> 5 的最高差为 3
5 -> 4 -> 6 -> 4 -> 5 的最高差为 2
样例 3 说明：
图中存在一条高度全为 1 的路径，这条最优路径的最高差为 0
数据范围和约定
对于 10% 的数据，存在一条从起点到终点高度不变的路径；
对于另外 20% 的数据，1<=n,m<=3；
对于另外 30% 的数据，1<=G[i][j]<=100；
对于全部数据，1<=n,m<=200，1<=G[i][j]<=108；
