题目描述

Arsh从事回收旧电路板的工作，他最近发现了一个R行C列的矩形方格电路板。

电路板上的每个方格区域都具有一定的厚度（以毫米为单位）。

其中第r行第c列的电路板方格厚度记为$V_{r,c}$。

如果说一个电路板，满足在它的每一行中，最厚的方格区域的厚度与最薄的方格区域的厚度之间的厚度差均不大于K，则我们认为这块电路板是好电路板。

由于这个电路板整体可能不是一个好电路板，所以Arsh想从中找到一个好的子电路板。

通过从原始板上选择一个轴对齐的子矩形，并将子矩形内的电路板方格区域全部取出，就可以获得一块子电路板。

请你帮帮Arsh，找到原始板中最大的好子电路板，并求出该子电路板所占的方格区域数量。

输入格式

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含三个整数R,C,K。

接下来R行，每行包含C个整数，其中第r行第c个整数表示$V_{r,c}$,即电路板中第r行第c列方格区域的厚度。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为“Case #x: y”，其中x是组别编号（从1开始），y为最大好子电路板包含的方格区域数量。

数据范围

$ 1≤T≤10 $,
$ 1≤R,C≤300 $,
$ 0≤V_{i, j}≤1000 $,
$ 0≤K≤1000 $

样例

输入样例1：

3
1 4 0
3 1 3 3
2 3 0
4 4 5
7 6 6
4 5 0
2 2 4 4 20
8 3 3 3 12
6 6 3 3 3
1 6 8 6 4

输出样例1：

Case #1: 2
Case #2: 2
Case #3: 6

算法1

(扫描法) $O(nm^2)$

• 此处采用的操作为：枚举每行窗口的大小，再枚举该窗口的左端点，再去枚举每行
• 每次拓宽窗口长度大小时，都要保留上次窗口所求窗口内最大值和最小值之差。
• 需要注意的就是 我们初始电路板面积的最小值为原电路板的行数。

时间复杂度

枚举区间，左端点，行数 所以总时间复杂度$O(nm^2)$

参考文献

Google KickStart

C++ 代码

#include<iostream>
using namespace std;

const int N = 310;

int n, m, k;
int a[N][N];
int minv[N][N], maxv[N][N];

int main()
{
    int T;
    cin >> T;
    int cnt = 1;
    while(T --){
        cin >> n >> m >> k;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> a[i][j];
                minv[i][j] = maxv[i][j] = a[i][j];
            }
        }

        int res = n;
        for(int len = 2; len <= m; len ++){
            for(int i = 1; i + len - 1 <= m; i ++){
                for(int j = 1, s = 0; j <= n; j++){
                    int &t_min = minv[j][i], &t_max = maxv[j][i];
                    t_min = min(t_min, a[j][i + len - 1]);
                    t_max = max(t_max, a[j][i + len - 1]);

                    if(t_max - t_min <= k){
                        s ++;
                        res = max(res, s * len);
                    }else s = 0;
                }
            }
        }
        printf("Case #%d: %d\n", cnt++, res);
    }
    return 0;
}