P1387. 约束最密集子矩阵

描述

给定一个$m \times n$矩阵$A = [a_{ij}]$，该问题的目标是找到$A$的一个（连续的）子矩阵，其大小至少为$R$行和至少$C$列，使得子矩阵中数字的平均值最大化。

设$A = [a_{ij}]$是一个$m \times n$矩阵。那么一个$p \times q$矩阵$B = [b_{ij}]$是$A$的一个（连续的）子矩阵，当存在一个固定的有序对$(K,L)$，使得对于每个$(i, j)$对，都有$b_{ij} = a_{i + K, j + L}$；注意$1 \leq i \leq p$且$1 \leq j \leq q$。例如，

矩阵$A= [a_{ij}]$的密度是$A$中所有元素的平均值，即$密度=\frac{\sum_{i = 1}^{m}\sum_{j = 1}^{n}a_{ij}}{mn}$。注意，找到给定矩阵的最密集子矩阵在一般情况下很简单，就是矩阵中的最大元素。另一方面，当要求找到大小至少为$R \times C$的子矩阵且其密度最大化时，这个问题就变得有趣了。

编写一个程序来找到$A$的大小至少为$R \times C$的最密集子矩阵。

输入

有若干组整数矩阵。输入是一个整数列表。在每组中，第一行的 4 个整数表示矩阵的大小，$m$和$n$表示一个$m \times n$矩阵，以及约束子矩阵的大小$R$和$C$。注意，$m$、$n$、$R$、$C$中的每一个最大可以是 200。在这四个整数之后，会有$m$行表示矩阵的$m$行；每行恰好包含$n$个整数，这些整数是该行中的元素。矩阵中每个元素的值在 0 到 800 的范围内，并且大多数元素小于 100。因此，对于特定的矩阵，总共有$mn$个整数。

这些矩阵会按照上述模式在输入中重复出现。整数$m = 0$表示输入的结束。

输出

对于输入的每个矩阵，找到大小至少为$R$行和$C$列的最密集子矩阵。通过打印四个索引来指定子矩阵的左上角和右下角来输出子矩阵。例如，一行

$r_1\ c_1\ r_2\ c_2$

表示一个子矩阵，其左上角为$(r_1, c_1)$，右下角为$(r_2, c_2)$。输出一个单独的星号*表示输出的结束。

为了答案的唯一性，如果两个子矩阵具有相同的密度，只输出其四个角的索引$(r_1, c_1, r_2, c_2)$字典序较小的矩阵。例如，如果两组索引是$(4, 3, 18, 9)$和$(7, 1, 14, 8)$，那么只输出第一个子矩阵，因为其角的索引字典序较小。

输入数据 1

3 4 2 1
150 500 150 800
1 200 100 300
400 800 80 400
4 2 3 2
400 800
200 500
100 200
600 600
0 

输出数据 1

1 4 2 4
1 1 4 2
* 

提示

暴力算法会导致时间限制超出。

来源

台湾 2001