题解 | # D 迷阵#

先考虑暴力，我们可以3000*3000*n*n枚举所有的情况，最小值最大值是否可行。　
然后可以考虑枚举最小值，二分最大值看是否合法，或者直接二分答案，总感觉会Ｔ(但人家的代码都过了)
但再考虑一下的话，当枚举一个最大值的时候，我们需要让最小值尽可能大，所以最小值具有单调性，就可以枚举最大值，最小值对应着跑。
复杂度3000*n*n　　300多ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
typedef  long long ll;
using namespace std;
#define rep(i,j,n) for(ll i=j;i<=n;i++)
#define per(i,j,n) for(ll i=j;i>=n;i--)
#define pr(x) printf("%lld\n",x)
#define pb(x) push_back(x)
typedef unsigned long long ull;
typedef unsigned int us;
const ll INF=1e18+7;const double eps=1e-8,pi=acos(-1);

const ll maxx=1e6+700;

inline bool read(ll &num){char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,k;
ll a[110][110];
ll ans=0;
ll dx[4]={0,0,1,-1};
ll dy[4]={1,-1,0,0};
ll b[12000];
ll judge(ll x,ll y)
{
    if(x&&y&&x<=n&&y<=n) return 1;
    return 0;
}
ll vis[110][110];
ll maxl,minl;
void dfs(ll x,ll y)
{
    if(a[x][y]<=maxl && a[x][y]>=minl )
    {
        vis[x][y]=1;
        rep(i,0,3)
        {
            ll px=x+dx[i],py=y+dy[i];
            if(!vis[px][py]&& judge(px,py)) {
                dfs(px,py);
            }
        }
    }
    else return ;
}
int main()
{
    ll t,x,y;
    ll n1,n2,m1,m2;
    cin>>n;
    int cnt=0;
    rep(i,1,n)
    rep(j,1,n)
    {
        cin>>a[i][j];
        b[++cnt]=a[i][j];
    }

    ll res=INF;
    sort(b+1,b+1+cnt);
    cnt=unique(b+1,b+1+cnt)-(b+1);
    ll pos1=1,pos2=2;
    
    rep(pos2,1,cnt)
    {
        while(1)
        {
            memset(vis,0,sizeof(vis));
            maxl = b[pos2];
            minl = b[pos1];
            //printf("%lld %lld\n",maxl,minl);
            dfs(1,1);
            if(vis[n][n]==1)
            {
                res=min(res,maxl-minl);
                pos1++;
                //printf("%lld %lld\n",maxl,minl);
            }
            else break;
        }
    }
    
    pr(res);
    return 0;


}