pku2110.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 87 行

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

int map[size][size];
int vis[size][size];
int High, Low;
int N;
int found;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

int In(int x, int y)
{
	return x >= 0 && y >= 0 && x < N && y < N;
}

void DFS(int x, int y)
{
	int i, nx, ny;
	if (x == N - 1 && y == N - 1)
	{
		found = 1;
	}
	if (found)
	{
		return;
	}
	vis[x][y] = 1;
	for (i = 0; i < 4; i++)
	{
		nx = x + dir[i][0];
		ny = y + dir[i][1];
		if (In(nx, ny) && !vis[nx][ny] && map[nx][ny] >= Low && map[nx][ny] <= High)
		{
			DFS(nx, ny);
		}
	}
}

void Solve()
{
	int i, j;
	int min, max, mid;
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			scanf("%d", &map[i][j]);
		}
	}
	min = 0;
	max = 111;
	while (min < max)
	{
		found = 0;
		mid = (min + max) / 2;
		for (Low = 0; found == 0 && Low < 111; Low++)
		{
			High = Low + mid;
			if (map[0][0] < Low || map[N - 1][N - 1] < Low || map[0][0] > High || map[N - 1][N - 1] > High)
			{
				continue;
			}
			memset(vis, 0, sizeof(vis));
			DFS(0, 0);
		}
		if (found)
		{
			max = mid;
		}
		else
		{
			min = mid + 1;
		}
	}
	printf("%d\n", min);
}

int main()
{
	while (EOF != scanf("%d", &N))
	{
		Solve();
	}	
	return 0;
}