看到此题，第一反应是枚举差值，然后DFS，后来一想，二分也可以，而且速度加快很多，就果断二分之了
刚开始写的比较挫，直接用的差值在地图里搜，维护一个最大值，一个最小值，然后如果找不到路就回溯，这样果断TLE了。
后来一想，不用这么搞，回溯太费时间了，就对每个差值，枚举下界，然后在范围内的才能走，这就不需要回溯了，就相当于最裸的走迷宫了。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 105
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int a[MAXN][MAXN], n;
int mi, mx;
int xx[] = {0, 0, 1, -1};
int yy[] = {1, -1, 0, 0};
int used[MAXN][MAXN];
bool dfs(int up, int down, int x, int y)
{if(x == n && y == n) return true;for(int i = 0; i < 4; i++){int tx = x + xx[i];int ty = y + yy[i];if(tx <= 0 || ty <= 0 || tx > n || ty > n || used[tx][ty]) continue;if(a[tx][ty] >= up && a[tx][ty] <= down){used[tx][ty] = 1;if(dfs(up,down, tx,ty)) return true;}}return false;
}
int main()
{while(scanf("%d", &n) != EOF){int fk = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){scanf("%d", &a[i][j]);}int low = 0, high = 120;int ans = 120;while(low <= high){int mid = (low + high) >> 1;int mi = max(a[1][1] - mid, 0);int flag = 0;for(int i = mi; i <= a[1][1]; i++){memset(used, 0, sizeof(used));used[1][1] = 1;if(dfs(i, i + mid, 1, 1)){flag = 1;break;}}if(flag){ans = min(ans, mid);high = mid - 1;}else low = mid + 1;}printf("%d\n", ans);}return 0;
}