记录编号	240963	评测结果	AAAAAAAAAA
题目名称	定向越野	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2016-03-24 10:02:31	内存使用	0.45 MiB

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int n,a[110][110],qx[10020],qy[10020],pd,MX,MN;
int fx[6]={0,0,1,-1};
int fy[6]={1,-1,0,0};
bool vis[110][110];
/*void dfs(int x,int y,int K)
{
    int MX1,MN1,xx,yy,i;
    if(pd==1)return;
    if(MX-MN>K)return;
    //if(x<1||x>n||y<1||y>n)return;
    if(x==n&&y==n)
    {
        if(MX-MN<=K)pd=1;
        return;
    }
    for(i=0;i<=3;i++)
    {
        xx=x+fx[i];
        yy=y+fy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&vis[xx][yy]==false)
        {
            MX1=MX;MN1=MN;
            if(a[xx][yy]>MX)MX=a[xx][yy];
            if(a[xx][yy]<MN)MN=a[xx][yy];
            vis[xx][yy]=true;
            dfs(x+fx[i],y+fy[i],K);
            vis[xx][yy]=false;
            MX=MX1;MN=MN1;
        }
    }
}*/
int BFS(int low,int high)
{
    int head,tail,ux,uy,vx,vy,i;
    if(a[1][1]<low||a[1][1]>high)return 0;
    head=0;tail=1;
    qx[tail]=1;qy[tail]=1;
    memset(vis,false,sizeof(vis));vis[1][1]=true;
    while(head!=tail)
    {
        head++;if(head==10010)head=0;
        ux=qx[head];uy=qy[head];
        for(i=0;i<=3;i++)
        {
            vx=ux+fx[i];
            vy=uy+fy[i];
            if(vx>=1&&vx<=n&&vy>=1&&vy<=n&&a[vx][vy]>=low&&a[vx][vy]<=high&&vis[vx][vy]==false)
            {
                vis[vx][vy]=true;
                tail++;if(tail==10010)tail=0;
                qx[tail]=vx;qy[tail]=vy;
                if(vx==n&&vy==n)return 1;
            }
        }
    }
    return 0;
}
int Judge(int k)
{
    int low;
    //MX=a[1][1];MN=a[1][1];
    //memset(vis,false,sizeof(vis));vis[1][1]=true;pd=0;
    for(low=0;low+k<=200;low++)if(BFS(low,low+k)==1)return 1;
    return 0;
}
int main()
{
    freopen("adven.in","r",stdin);
    freopen("adven.out","w",stdout);
    int i,j,l,r,mid,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    l=0;r=200;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(Judge(mid)==1){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}