分支下限法，确定下届然后搜索上界。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=2110
#include <stdio.h>

int map[100][100];

int used[100][100];

int move[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };

int n, nmin, nmax, count;

int dfs ( int h, int l, int min, int high )
{

    int th, tl;

    if ( used[h][l] == count )
    {
        return 0;
    }
    used[h][l] = count;

    if ( map[h][l] >= min && map[h][l] <= min+high )
    {
        if ( h == n-1 && l == n-1 )
        {
            return 1;
        }

        for ( int i=0; i<4; i++ )
        {
            th = h + move[i][0];
            tl = l + move[i][1];

            if ( th>=0 && th<n && tl>=0 && tl<n )
            {
                if ( dfs ( th, tl, min, high ) )
                {
                    return 1;
                }
            }
        }
    }

    return 0;
}

int judge ( int high )
{

    for ( int i=nmin; i<=nmax; i++ )
    {
        count ++;
        if ( dfs ( 0, 0, i, high ) )
        {
            return 1;
        }
    }
    return 0;
}

int main ()
{

    while ( scanf ( "%d", &n ) != EOF )
    {
        nmax = -1;
        nmin = 0x7fffffff;
        for ( int i=0; i<n; i++ )
        {
            for ( int j=0; j<n; j++ )
            {
                scanf ( "%d", &map[i][j] );
                if ( nmin > map[i][j] )
                {
                    nmin = map[i][j];
                }
                if ( nmax < map[i][j] )
                {
                    nmax = map[i][j];
                }
            }
        }

        int l, r, mid;
        l = 0, r  = nmax - nmin;
        count = 0;
        while ( l <= r )
        {
            mid = ( l + r ) / 2;
            if ( judge ( mid ) )
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        printf ( "%d\n", l );
    }
    return 0;
}