2310.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2310 on 2006-08-07 at 11:03:57 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 128;
const int DIR[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

int m[N][N], n;
bool vst[N][N];

bool legal(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
bool find(int, int, int, int);

int main()
{
	int i, j, t, T;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n);
		int y = 1 << 30, z = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				scanf("%d", &m[i][j]);
				y = min(m[i][j], y);
				z = max(m[i][j], z);
			}
		printf("Scenario #%d:\n", t+1);
		int x = min(m[0][0], m[n-1][n-1]), best = 1 << 30;
		for(i = y; i <= x; i++) {
			int l = i, h = z+1;
			while(h != l) {
				int mid = (l+h)/2;
				memset(vst, false, sizeof(vst));
				if(find(0, 0, i, mid)) h = mid;
				else l = mid+1;
			}
			if(h != z+1) best = min(best, h-i);
		}
		printf("%d\n\n", best);
	}
	
	return 0;
}

bool find(int x, int y, int l, int h)
{
	if(m[x][y] > h || m[x][y] < l) return false;
	vst[x][y] = true;
	if(x == n-1 && y == n-1) return true;
	else {
		int i;
		for(i = 0; i < 4; i++) {
			int cx = x+DIR[i][0], cy = y+DIR[i][1];
			if(!legal(cx, cy) || vst[cx][cy]) continue;
			if(find(cx, cy, l, h)) return true;
		}
		return false;
	}
}