这道题可以用RMQ来做。
RMQ原本是对一个数列进行预处理,这里我们只需要对矩阵的每一行都进行一次预处理就好。然后枚举可能的所有的正方形,用RMQ查询这个正方形里面的最大值和最小值,不断更新最大值与最小值之差就好。
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int inf=1e9+5; //inf记得开的大一点,否则会出错的
const int maxn=1e3+5;
int map[maxn][maxn];
int dp1[maxn][maxn][10],dp2[maxn][maxn][10]; //dp1记录最大值,dp2记录最小值
int min_(int x,int y) //可以用algorithm头文件里的比较函数,但这里特意自己写了一个是防止超时(STL速度是比较慢的)
{
return x<y? x:y;
}
int max_(int x,int y)
{
return x>y? x:y;
}
int main()
{
int a,b,n;
scanf("%d%d%d",&a,&b,&n);
for(int i=1;i<=a;++i)
for(int j=1;j<=b;++j)
scanf("%d",&map[i][j]);
if(n==1)
{
printf("0\n");
return 0;
}
for(int i=1;i<=a;++i) //逐行预处理
{
for(int j=1;j<=b;++j) dp1[i][j][0]=dp2[i][j][0]=map[i][j];
for(int j=1;(1<<j)<=b;++j)
for(int k=1;k+(1<<j)-1<=b;++k)
{
dp1[i][k][j]=max_(dp1[i][k][j-1],dp1[i][k+(1<<(j-1))][j-1]);
dp2[i][k][j]=min_(dp2[i][k][j-1],dp2[i][k+(1<<(j-1))][j-1]);
}
}
int ans=inf,k=0;
while((1<<(k+1))<=n) ++k;
for(int i=1;i<=a-n+1;++i) //枚举正方形的左上顶点来枚举正方形
for(int j=1;j<=b-n+1;++j)
{
int ma,mi,l,r;
l=j; r=j+n-(1<<k);
ma=max_(dp1[i][l][k],dp1[i][r][k]);
mi=min_(dp2[i][l][k],dp2[i][r][k]);
for(int p=i+1;p<=i+n-1;++p) //扫遍正方形的每一行
{
ma=max_(ma,max_(dp1[p][l][k],dp1[p][r][k]));
mi=min_(mi,min_(dp2[p][l][k],dp2[p][r][k]));
}
ans=min_(ans,ma-mi);
}
printf("%d\n",ans);
return 0;
}