记录详情

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 5;
int a, b, n, mp[maxn][maxn], ans = INT_MAX;
int rmax[maxn][maxn], rmin[maxn][maxn], cmax[maxn][maxn], cmin[maxn][maxn];
int q[maxn], head, tail;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> a >> b >> n;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            cin >> mp[i][j];
    for (int i = 1; i <= a; i++) {
        head = tail = 0;
        for (int j = 1; j <= b; j++) { //求每行区间最大值 
            while (head <= tail && q[head] + n <= j) head++;
            while (head <= tail && mp[i][q[tail]] < mp[i][j]) tail--;
            q[++tail] = j;
            if (j >= n) rmax[i][j - n + 1] = mp[i][q[head]];
        }
        head = tail = 0;
        for (int j = 1; j <= b; j++) { //求每行区间最小值
            while (head <= tail && q[head] + n <= j) head++;
            while (head <= tail && mp[i][q[tail]] > mp[i][j]) tail--;
            q[++tail] = j;
            if (j >= n) rmin[i][j - n + 1] = mp[i][q[head]];
        }
    }
    for (int j = 1; j <= b - n + 1; j++) {
        head = tail = 0;
        for (int i = 1; i <= a; i++) { //在新矩阵上，求每列区间最大值
            while (head <= tail && q[head] + n <= i) head++;
            while (head <= tail && rmax[q[tail]][j] < rmax[i][j]) tail--;
            q[++tail] = i;
            if (i >= n) cmax[i - n + 1][j] = rmax[q[head]][j];
        }
        head = tail = 0;
        for (int i = 1; i <= a; i++) { //在新矩阵上，求每列区间最小值
            while (head <= tail && q[head] + n <= i) head++;
            while (head <= tail && rmin[q[tail]][j] > rmin[i][j]) tail--;
            q[++tail] = i;
            if(i >= n) cmin[i - n + 1][j] = rmin[q[head]][j];
        }
    }
    for (int i = 1; i <= a - n + 1; i++) 
        for (int j = 1; j <= b - n + 1; j++)
            ans = min(ans, cmax[i][j] - cmin[i][j]);
    cout << ans << endl;
    return 0;
}