记录编号	240890	评测结果	AAAAAAAAAA
题目名称	定向越野	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.324 s
提交时间	2016-03-24 07:03:57	内存使用	0.37 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=110,INF=0x7fffffff/2;
int N;
int mp[SIZEN][SIZEN];
int mi=INF,ma=0;
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=N;j++)
		{
			scanf("%d",&mp[i][j]);
			mi=min(mp[i][j],mi);ma=max(mp[i][j],ma);
		}
	}
}
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int ans=INF;
bool on(int x,int y)
{
	if(x<=0||y<=0||x>N||y>N) return 0;
	return 1;
}
bool vis[SIZEN][SIZEN];
bool dfs(int x,int y,int l,int r)
{
	if(mp[x][y]<l||mp[x][y]>r) return 0;
	if(x==N&&y==N) return 1;
	//cout<<x<<" "<<y<<endl;
	vis[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(!on(nx,ny)||vis[nx][ny]) continue;
		if(dfs(nx,ny,l,r)) return 1;
	}
	return 0;
}
void work()
{
	for(int i=mi;i<=ma;i++)
	{
		for(int j=i;j<=ma;j++)
		{
			if(j-i>=ans) continue;
			memset(vis,0,sizeof(vis));
			if(dfs(1,1,i,j)) ans=j-i;
		}
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("adven.in","r",stdin);
	freopen("adven.out","w",stdout);
	read();
	work();
	return 0;
}