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

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 110
using namespace std;
ifstream in("adven.in");
ofstream out("adven.out");
int A[N][N]={0};
int n,m=0;
int ans=0;
int INF=(1<<28);
bool l[N][N]={0};
int f[N][N]={0};
class point
{
public:
	int x,y;
	void make(int a,int b)
	{
		x=a;
		y=b;
	}
	void print()
	{
		out<<x<<' '<<y<<endl;
	}
}dir[5];
point operator +(point a,point b)
{
	point c;
	c.x=a.x+b.x;
	c.y=a.y+b.y;
	return c;
}
point make(int a,int b)
{
	point e;
	e.make(a,b);
	return e;
}
void read()
{
	int i,j;
	in>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			in>>A[i][j];
			m=max(m,A[i][j]);
		}
	}
}
bool legal(point u)
{
	if(u.x>=1&&u.x<=n&&u.y>=1&&u.y<=n&&l[u.x][u.y]==0)return 1;
	return 0;
}
int SPFA(int limit)
{
	int i,j;
	point u,v;
	queue<point> q;
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)
	{
		f[i][j]=INF;
		l[i][j]=0;
	}
	l[1][1]=1;
	f[1][1]=0;
	q.push(make(1,1));
	if(A[1][1]<limit)return INF;
	f[1][1]=A[1][1];
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		//u.print();
		//l[u.x][u.y]=0;
		for(i=1;i<=4;i++)
		{
			v=u+dir[i];
			if(!legal(v))continue;
			if(A[v.x][v.y]<limit)continue;
			if(f[v.x][v.y]>max(f[u.x][u.y],A[v.x][v.y]))
			{
				f[v.x][v.y]=max(f[u.x][u.y],A[v.x][v.y]);
				//if(!l[v.x][v.y])
				//{
					//l[v.x][v.y]=1;
					q.push(v);
				//}
			}
		}
	}
	//out<<endl;
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			out<<f[i][j]<<' ';
		}
		out<<endl;
	}
	out<<endl;*/
	return f[n][n];
}
void work()
{
	int low,High,temp;
	dir[1].make(1,0);
	dir[2].make(0,1);
	dir[3].make(0,-1);
	dir[4].make(-1,0);
	ans=INF;
	//out<<A[1][1]<<endl;
	for(low=0;low<=m;low++)
	{
		High=SPFA(low);
		//out<<High<<' '<<low<<endl;
		temp=High-low;
		if(ans>temp)ans=temp;
	}
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}