MoutainWalking

#include <bits/stdc++.h>

#define maxH 115
#define maxN 105

using namespace std;

int n, h, l, ans = maxH, a[maxN][maxN];
int dx[] = {-1, 0, 1, 0},
    dy[] = {0, 1, 0, -1};
bool visited[maxN][maxN];

bool ok(int x) {
    if (x >= 1 && x <= n) return true; else return false;
}

bool check(int mid) {
    queue <int> q;
    q.push(1); q.push(1);
    memset(visited, false, sizeof visited);
    visited[1][1] = true;

    while (!q.empty())
    {
        int ux = q.front(); q.pop();
        int uy = q.front(); q.pop();
        if (ux == n && uy == n) return true;
        visited[ux][uy] = true;
        for (int k=0; k<4; ++k)
        {
            int vx = ux + dx[k], vy = uy + dy[k];
            if (ok(vx) && ok(vy) && !visited[vx][vy] && abs(a[ux][uy] - a[vx][vy]) <= mid)
            {
                q.push(vx); q.push(vy);
            }
        }
    }

    if (!visited[n][n]) return false; else return true;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("MTWALK.inp", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &n);
    for (int i=1; i<=n; ++i)
        for (int j=1; j<=n; ++j) scanf("%d", &a[i][j]);

    l = 0; h = maxH;
    while (l <= h)
    {
        int mid = (l + h) / 2;
        if (check(mid))
        {
            ans = mid;
            h = mid - 1;
        } else l = mid + 1;
    }

    printf("%d", ans);

    return 0;
}