3156468_ac_63ms_412k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int n;
int height[101][101];

int valid(int i,int j)
{
	return i >= 0 && j >= 0 &&  i < n && j < n;
}

int mov[][2] = {{0,1},{0,-1},{1,0},{-1,0}};

int map[101][101];
int visited[101][101];

void flood_fill(int x,int y)
{
	int i;

	visited[x][y] = 1;
	for(i = 0; i < 4; i++)
	{
		if(valid(x+mov[i][0],y+mov[i][1])&&visited[x+mov[i][0]][y+mov[i][1]]==0&&map[x+mov[i][0]][y+mov[i][1]]==1)
		{
			flood_fill(x+mov[i][0],y+mov[i][1]);
		}
	}
}

int can(int h)
{
	int i, max, min;
	int l, k;

	min = height[0][0] > height[n-1][n-1] ? height[0][0] - h : height[n-1][n-1]-h;
	if(min < 0)
	{
		min = 0;
	}
	max = height[0][0] < height[n-1][n-1] ? height[0][0] : height[n-1][n-1];
	for(i = min; i <= max; i++)
	{
		for(l = 0; l < n; l++)
		{
			for(k = 0; k < n; k++)
			{
				map[l][k] = (height[l][k] >= i && height[l][k] <= i+h);
			}
		}
		memset(visited,0,sizeof(visited));
		flood_fill(0,0);
		if(visited[n-1][n-1]==1)
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	int i, j;
	int min, max, mid;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			scanf("%d",&height[i][j]);
		}
	}
	min = 0;max = 110;
	while(min < max)
	{
		mid = (min+max)>>1;
		if(can(mid))
			max = mid;
		else
			min = mid+1;
	}
	printf("%d\n",min);
	return 0;
}