迷阵
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

学姐无意间走入了一个迷阵，迷阵可以看成一个的矩阵，每个位置有一个属性，学姐每次只能往相邻格点移动，每个格点都可以被经过0次或任意次,已知对于两个格点，当且仅当时认为这两点相邻,学姐打算从 走到，但学姐走出迷阵后一段时间内会精神混乱，精神混乱的时间取决于学姐在迷阵中所经过的所有格点（包括起点和终点）的权值的极差(最大值减去最小值)。现在学姐想知道走出迷宫精神混乱时间最少是多少。

输入描述:

第一行一个正整数n(n≤100)，表示迷阵大小
接下来n行，每行n个数，表示wij(0≤wij≤3000)

输出描述:

一个数，表示走到(n,n)时得到的最小的T
示例1

输入

复制 
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

输出

复制 
2

说明

1->1->2->2->0->2->0->2->1
路径上最大值M1=2，最小值M2=0，T=M1-M2=2
显然路径方案不唯一

备注:

对于15%的数据： 1≤n≤20 0≤wij≤100
对于45%的数据： 1≤n≤100 0≤wij≤100，其中有另5%保证1≤n≤100 0≤wij≤5
对于100%的数据： 1≤n≤100 0≤wij≤3000