记录编号	241084	评测结果	AAAAAAAAAA
题目名称	定向越野	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.366 s
提交时间	2016-03-24 14:51:23	内存使用	0.40 MiB

//KZNS
#include <fstream>
#include <queue>
#include <utility>
using namespace std;
//
ifstream fin ("adven.in");
ofstream fout ("adven.out");
const int Nmax = 103;
const int INF = 0x7fffffff;
typedef pair<int, int> pr;
//
int N;
int gp[Nmax][Nmax];
bool ex[203] = {0};
int ed[Nmax][Nmax] = {0};
int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool lsd[Nmax][Nmax] = {0};
int bst = INF;
//
void rin() {
	fin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++) {
			fin >> gp[i][j];
			ex[gp[i][j]] = true;
		}
}
int spfa(int low) {
	if (gp[1][1] < low)
		return INF;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			ed[i][j] = INF;
	ed[1][1] = gp[1][1];
	queue<pr> ls;
	ls.push(make_pair(1, 1));
	lsd[1][1] = true;
	pr u;
	int x, y;
	int x1, y1;
	while (!ls.empty()) {
		u = ls.front();
		x = u.first;
		y = u.second;
		ls.pop();
		lsd[x][y] = false;
		for (int i = 0; i < 4; i++) {
			x1 = x+mv[i][0];
			y1 = y+mv[i][1];
			if (0 < x1 && x1 <= N && 0 < y1 && y1 <= N) {
				if (!(gp[x1][y1] < low)) {
					if (max(ed[x][y], gp[x1][y1]) < ed[x1][y1]) {
						ed[x1][y1] = max(ed[x][y], gp[x1][y1]);
						if (!lsd[x1][y1]) {
							ls.push(make_pair(x1, y1));
							lsd[x1][y1] = true;
						}
					}
				}
			}
		}
	}
	return ed[N][N];
}
//
int main() {
	rin();
	int u;
	for (int i = 203; i >= 0; i--) {
		if (ex[i]) {
			u = spfa(i);
			bst = min(bst, u-i);
		}
	}
	fout << bst;
	return 0;
}
//UBWH