1 //BZOJ 1047  2 //by Cydiater  3 //2016.9.17  4 #include <iostream>  5 #include <cstdio>  6 #include <cstdlib>  7 #include <cstring>  8 #include <cmath>  9 #include <ctime> 10 #include <map> 11 #include <iomanip> 12 #include <string> 13 #include <algorithm> 14 #include <queue> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 const int MAXN=1e3+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22     char ch=getchar();int x=0,f=1; 23     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 int N,M,K,a[MAXN][MAXN],head[MAXN],tail[MAXN],lable_max[MAXN][MAXN],lable_min[MAXN][MAXN],q[MAXN][MAXN],extro_q[MAXN],extro_head,extro_tail,ans=oo; 28 namespace solution{ 29     inline void push(int co,int id){q[co][++tail[co]]=id;} 30     void init(){ 31         N=read();M=read();K=read(); 32         up(i,1,N)up(j,1,M)a[i][j]=read(); 33     } 34     void Queue_max(){ 35         memset(tail,0,sizeof(tail)); 36         up(i,1,N)head[i]=1; 37         up(i,1,N)up(j,1,K){ 38             while(head[i]<=tail[i]&&a[i][j]>a[i][q[i][tail[i]]])tail[i]--; 39             push(i,j);//load y 40         } 41         extro_head=1;extro_tail=0; 42         up(i,1,K-1){ 43             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 44             extro_q[++extro_tail]=i;//load x 45         } 46         up(i,K,N){ 47             while(i-extro_q[extro_head]+1>K&&extro_head<=extro_tail)extro_head++; 48             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 49             extro_q[++extro_tail]=i;//load x 50             lable_max[i][K]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]]; 51         } 52         up(j,K+1,M){ 53             up(i,1,N){ 54                 while(j-q[i][head[i]]+1>K&&head[i]<=tail[i])head[i]++; 55                 while(head[i]<=tail[i]&&a[i][j]>a[i][q[i][tail[i]]])tail[i]--; 56                 push(i,j);//load y 57             } 58             extro_head=1;extro_tail=0; 59             up(i,1,K-1){ 60                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 61                 extro_q[++extro_tail]=i;//load x 62             } 63             up(i,K,N){ 64                 while(i-extro_q[extro_head]+1>K&&extro_head<=extro_tail)extro_head++; 65                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]>a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 66                 extro_q[++extro_tail]=i;//load x 67                 lable_max[i][j]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]]; 68             } 69         } 70     } 71     void Queue_min(){ 72         memset(tail,0,sizeof(tail)); 73         up(i,1,N)head[i]=1; 74         up(i,1,N)up(j,1,K){ 75             while(head[i]<=tail[i]&&a[i][j]<a[i][q[i][tail[i]]])tail[i]--; 76             push(i,j);//load y 77         } 78         extro_head=1;extro_tail=0; 79         up(i,1,K-1){ 80             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 81             extro_q[++extro_tail]=i;//load x 82         } 83         up(i,K,N){ 84             while(i-extro_q[extro_head]+1>K&&extro_head<=extro_tail)extro_head++; 85             while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 86             extro_q[++extro_tail]=i;//load x 87             lable_min[i][K]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]]; 88         } 89         up(j,K+1,M){ 90             up(i,1,N){ 91                 while(j-q[i][head[i]]+1>K&&head[i]<=tail[i])head[i]++; 92                 while(head[i]<=tail[i]&&a[i][j]<a[i][q[i][tail[i]]])tail[i]--; 93                 push(i,j);//load y 94             } 95             extro_head=1;extro_tail=0; 96             up(i,1,K-1){ 97                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--; 98                 extro_q[++extro_tail]=i;//load x 99             }100             up(i,K,N){101                 while(i-extro_q[extro_head]+1>K&&extro_head<=extro_tail)extro_head++;102                 while(extro_head<=extro_tail&&a[i][q[i][head[i]]]<a[extro_q[extro_tail]][q[extro_q[extro_tail]][head[extro_q[extro_tail]]]])extro_tail--;103                 extro_q[++extro_tail]=i;//load x104                 lable_min[i][j]=a[extro_q[extro_head]][q[extro_q[extro_head]][head[extro_q[extro_head]]]];105             }106         }        107     }108     void slove(){109         Queue_max();110         Queue_min();111     }112     void output(){113         /*up(i,1,N){114             up(j,1,M)cout<<lable_max[i][j]<<‘ ‘;115             cout<<endl;116         }117         puts("");118         up(i,1,N){119             up(j,1,M)cout<<lable_min[i][j]<<‘ ‘;120             cout<<endl;121         }122         puts("");*/123         up(i,K,N)up(j,K,M)ans=min(ans,lable_max[i][j]-lable_min[i][j]);124         cout<<ans<<endl;125     }126 }127 int main(){128     //freopen("input.in","r",stdin);129     using namespace solution;130     init();131     slove();132     output();133     return 0;134 }