2019.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define LOW -1
#if debug
    #define NMAX 10
#else
    #define NMAX 252
#endif
int N,B,K;
int a[NMAX][NMAX];
int y,x;

int l[NMAX][NMAX],d[NMAX][NMAX],h[NMAX][NMAX];
int main()
{

#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j,k;
	scanf("%d%d%d",&N,&B,&K);
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			scanf("%d",&a[i][j]);
		
		}
	int max,min;
	for(i=1;i<=N;i++)
	{
		j=1;
		max=LOW;
		min=INF;
		for(k=j;k<=j+B-1;k++)
		{
			if(max<a[i][k])
				max=a[i][k];
			if(min>a[i][k])
				min=a[i][k];
		}
		h[i][j]=max;
		l[i][j]=min;
		for(j=2;j<=N-B+1;j++)
		{
			
			if(a[i][j-1]!=h[i][j-1])
				h[i][j]=h[i][j-1]>a[i][j+B-1]?h[i][j-1]:a[i][j+B-1];
			else
			{
				h[i][j]=LOW;
				for(k=j;k<=j+B-1;k++)
				{
					if(h[i][j]<a[i][k])
						h[i][j]=a[i][k];
				}
			}
			if(a[i][j-1]!=l[i][j-1])
				l[i][j]=l[i][j-1]<a[i][j+B-1]?l[i][j-1]:a[i][j+B-1];
			else
			{
				l[i][j]=INF;
				for(k=j;k<=j+B-1;k++)
				{
					if(l[i][j]>a[i][k])
						l[i][j]=a[i][k];
				}
			}
		}

	
	}
	for(i=1;i<=N-B+1;i++)
	{
		for(j=1;j<=N-B+1;j++)
		{
			max=LOW;
			min=INF;
			for(k=i;k<=i+B-1;k++)
			{
				if(max<h[k][j])
					max=h[k][j];
				if(min>l[k][j])
					min=l[k][j];
			}
			d[i][j]=max-min;
		}
	}
	int x,y;
	while(K--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",d[x][y]);
	}
	

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}