样例下载

【题目描述】

设有 $N × N$ 的网格图，每个方格中填有一个整数。

某人从图的左上角即第一行第一列的方格出发，目标是到达右下角即第 $N$ 行第 $N$ 列的方格。他可以向正东、正南、正西、正北四个方向行走，可以重复经过同一个方格，但不能走出网格图。每到达一个方格（包括初始和目标方格），他就会将方格中的数取走。到达右下角后，记他取走的数中最大的数为 $A$，最小的数为 $B$，并记 $S = A - B$。

问：他如何行走，可以使得 $S$ 的值最小？你只需要输出可以得到的 $S$ 的最小值。

【输入】

第一行： 一个整数 $N$

接下来是一个 $N × N$ 的整数矩阵 A，表示网格图中填着的数。

【输出】

一个整数，表示答案。

【样例输入】

5 
1 2 3 4 5 
2 2 2 2 2 
3 0 3 0 3 
4 5 1 2 3 
5 4 3 2 1

【样例输入】

2

【样例解释】

行走方案可能不唯一，以下是一种可能方案（加粗数字形成一条路径）：

1 2 3 4 5

2 2 2 2 2

3 0 3 0 3

4 5 1 2 3

5 4 3 2 1

【数据范围】

30% 的数据：$2 ≤ N ≤ 10$

100% 的数据：$2 ≤ N ≤ 100, 0 ≤ A_{ij} ≤ 200$