3156264_wa.cc

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

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

int n;
int height[201][201];

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 iabs(int num)
{
	return num > 0 ? num : -num;
}

int visited[201][201][2];
int max[20001], min[20001];
int que[20001][2];
int f, r;

int can(int h)
{
	int i, x, y;

	f = r = -1;
	++r;
	que[0][0] = 0;
	que[0][1] = 0;
	max[0] = min[0] = height[0][0];
	memset(visited,-1,sizeof(visited));
	visited[0][0][0] = visited[0][0][1] = height[0][0];
	while(f!=r)
	{
		++f;
		for(i = 0; i < 4; i++)
		{
			x = que[f][0]+mov[i][0];
			y = que[f][1]+mov[i][1];
			if(valid(x,y)==0||iabs(height[x][y]-max[f])>h||iabs(height[x][y]-min[f])>h)
			{
				continue;
			}
			if(visited[x][y][0]==-1||visited[x][y][0]>max[f]||visited[x][y][1]<min[f])
			{
				if(x==n-1&&y==n-1)
					return 1;
				++r;
				que[r][0] = x;
				que[r][1] = y;
				max[r] = max[f] > height[x][y] ? max[f] : height[x][y];
				min[r] = min[f] < height[x][y] ? min[f] : height[x][y];
				visited[x][y][0] = max[r];
				visited[x][y][1] = min[r];
			}
		}
	}
	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;
}