问题1458--走迷宫

1458: 走迷宫

时间限制: 1 Sec  内存限制: 128 MB
提交: 296  解决: 85
[状态] [讨论版] [提交] [命题人:]
题目描述

Dr.Kong设计的机器人卡多非常爱玩,它常常偷偷跑出实验室,在某个游乐场玩之不疲。这天卡多又跑出来了,在SJTL游乐场玩个不停,坐完碰碰车,又玩滑滑梯,这时卡多又走入一个迷宫。个迷宫是用一个N * N的方阵给出方阵中单元格中填充了一整数,表示走到这个位置的难度。

这个迷宫可以向上走,向下走,向右走,向左走,但是不能穿越对角线。迷宫的取胜规则很有意思,看谁能更快地找到一条路径,其路径上单元格最大难度值与最小难度值之差是最小的。当然了,或许这样的路径不是最短路径。

     机器人卡多现在在迷宫的左上角(第一行,第一列)而出口迷宫的右下角(第N行,第N列)。

卡多很聪明,很快就找到这样一条路径。你能找到吗?

输入

第一行:         N     表示迷宫是N*N方阵        (2 N 100)

接下来有N行, 每一行包含N个整数,用来表示单元格中难度 (0任意120)

输出

输出为个整数,表示路径上最高难度与和最低难

样例输入 Copy
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
样例输出 Copy
2