pku2922.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

/*
PKU2922
二分答案，枚举区间，广搜判是否可行 
*/

#include <stdio.h>
#include <string.h>
#define maxn 101

typedef struct Qnode
{
	int x, y;
}Qnode;

Qnode Q[maxn*maxn];
int map[maxn][maxn];
int v[maxn][maxn];
int N;
int F[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

int Min(int x, int y){return x < y ? x : y;}
int Max(int x, int y){return x > y ? x : y;}
int InMap(int x, int y){return x >= 0 && y >= 0 && x < N && y < N;}

void init()
{
	int i, j;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			scanf("%d", &map[i][j]);
}

int BFS(int low, int high)
{
	int head, tail;
	int x, y, nx, ny, i;
	Q[0].x= 0;
	Q[0].y= 0;
	memset(v, 0, sizeof(v));
	v[0][0] = 1;
	head = 0;
	tail = 1;
	while (head < tail)
	{
		x = Q[head].x;
		y = Q[head].y;
		for (i = 0; i < 4; i++)
		{
			nx = x + F[i][0];
			ny = y + F[i][1];
			if (InMap(nx, ny) && !v[nx][ny] && map[nx][ny] >= low && map[nx][ny] <= high)
			{
				if (nx == N - 1 && ny == N - 1)
					return 1;
				Q[tail].x = nx;
				Q[tail].y = ny;
				v[nx][ny] = 1;
				tail++;
			}
		}
		head++;
	}
	return 0;
}

int check(int mid)
{
	int i;
	for (i = Max(0, Max(map[0][0], map[N-1][N-1]) - mid);
			i <= Min(200, Min(map[0][0], map[N-1][N-1])); i++)
		if (BFS(i, i + mid))
			return 1;
	return 0;
}

int solve()
{
	int i;
	int min = 0;
	int max = 200;
	int mid;
	while (min < max)
	{
		mid = (min + max) >> 1;
		if (check(mid))
			max = mid;
		else
			min = mid + 1;
	}
	return min;
}

int main()
{
	int t, T;
	scanf("%d", &T);
	for (t = 1; t <= T; t++)
	{
		init();
		printf("Scenario #%d:\n%d\n\n", t, solve());
	}
	return 0;
}