1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef double db; 5 #define INF 0x3f3f3f3f 6 #define _for(i,a,b) for(int i = (a);i < b;i ++) 7 #define _rep(i,a,b) for(int i = (a);i > b;i --) 8 inline ll read() 9 { 10 ll ans = 0; 11 char ch = getchar(), last = ' '; 12 while(!isdigit(ch)) last = ch, ch = getchar(); 13 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 14 if(last == '-') ans = -ans; 15 return ans; 16 } 17 inline void write(ll x) 18 { 19 if(x < 0) x = -x, putchar('-'); 20 if(x >= 10) write(x / 10); 21 putchar(x % 10 + '0'); 22 } 23 int a,b,n; 24 int Log[1003]; 25 int maxx[1003][1003][11]; 26 int minn[1003][1003][11]; 27 void searchLog() 28 { 29 Log[0] = -1; 30 _for(i,1,max(a,b)+1) 31 Log[i] = Log[i/2]+1; 32 } 33 int query(int x,int y) 34 { 35 int xl = x+n-1,yl = y+n-1; 36 int s = Log[n]; 37 int MAX = max(maxx[x][y][s],max(maxx[xl-(1<<s)+1][yl-(1<<s)+1][s], 38 max(maxx[xl-(1<<s)+1][y][s],maxx[x][yl-(1<<s)+1][s]))); 39 40 int MIN = min(minn[x][y][s],min(minn[xl-(1<<s)+1][yl-(1<<s)+1][s], 41 min(minn[xl-(1<<s)+1][y][s],minn[x][yl-(1<<s)+1][s]))); 42 return MAX-MIN; 43 } 44 int main() 45 { 46 a = read(),b = read(), n = read(); 47 searchLog(); 48 _for(i,1,a+1) 49 _for(j,1,b+1) 50 minn[i][j][0] = maxx[i][j][0] = read(); 51 52 _for(r,1,Log[n]+1) 53 for(int i = 1;i + (1<<r) - 1 <= a;i ++) 54 for(int j = 1;j + (1<<r) -1 <= b;j ++) 55 { 56 maxx[i][j][r] = max(maxx[i][j][r-1],max(maxx[i][j+(1<<r-1)][r-1], 57 max(maxx[i+(1<<r-1)][j][r-1],maxx[i+(1<<r-1)][j+(1<<r-1)][r-1]))); 58 59 minn[i][j][r] = min(minn[i][j][r-1],min(minn[i][j+(1<<r-1)][r-1], 60 min(minn[i+(1<<r-1)][j][r-1],minn[i+(1<<r-1)][j+(1<<r-1)][r-1]))); 61 } 62 63 int ans = INT_MAX; 64 _for(i,1,a-n+2) 65 _for(j,1,b-n+2) 66 ans = min(ans,query(i,j)); 67 write(ans); 68 return 0; 69 }