HZNUOJ

走迷宫

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:387     AC:64     Score:97.37

Description

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

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

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

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

Input

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

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

Output

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

Samples

input
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
output
2

Source

第四届河南省大学生程序设计竞赛