解题思路分析 目标：找到一个大小至少为 R 行和 C 列的子矩阵，使得该子矩阵中数字的平均值最大化。 关键思路： 由于暴力枚举所有可能的子矩阵会导致时间复杂度太高（时间限制超出），所以采用优化的方法。 利用前缀和数组 sum 来快速计算子矩阵的元素和。对于矩阵 a，sum[i][j] 表示从矩阵左上角 (0, 0) 到 (i, j) 位置的子矩阵的元素和。 通过枚举不同的起始行 baseline 和结束行 endline（保证子矩阵行数至少为 R），在每一对起始行和结束行确定的范围内，对每一列计算在这个行范围内的子数组（子矩阵的列方向），利用 getmost 函数找到密度最大的至少 C 列的子数组。 getmost 函数通过滑动窗口的思想，维护一个队列来处理子数组的元素，从而高效地计算出密度最大的子数组。

实现步骤 输入矩阵信息： 读取矩阵的行数 m、列数 n、约束子矩阵的行数 r 和列数 c。 依次读取矩阵 a 的每一个元素。 计算前缀和数组： 首先初始化 sum[0][i] 为 a[0][i]。 然后对于 i > 0 的情况，通过 sum[i][j] = a[i][j] + sum[i-1][j] 计算每一个位置的前缀和。 枚举起始行和结束行： 从 baseline = 0 开始枚举，直到 baseline + r - 1 < m（保证子矩阵行数至少为 r）。 当 baseline > 0 时，对 sum 数组进行更新，将当前行范围以上的元素和减去，即 sum[i][j] -= a[baseline - 1][j]，这样 sum 数组在当前行范围内就表示相对独立的子矩阵的前缀和。 在当前行范围内枚举列方向的子数组： 对于每一个结束行 endline（endline >= baseline + r - 1），调用 getmost 函数，传入 sum[endline]（表示当前结束行的列方向数组）、列数 n、当前行范围内的行数 endline - baseline + 1，以及用于记录子数组起始和结束位置的变量 st 和 ed。

getmost 函数通过滑动窗口和队列维护，计算出在当前行范围内，列方向上密度最大的至少 C 列的子数组。 记录最优子矩阵： 如果当前计算得到的子矩阵密度 t 大于之前记录的最优密度 res，则更新 res 以及最优子矩阵的起始行 str、起始列 stc、结束行 edr 和结束列 edc。 输出结果： 输出最优子矩阵的左上角和右下角的索引（注意索引要加 1 以符合题目要求的从 1 开始计数）。 当所有矩阵处理完后，输出 * 表示输入结束。 getmost 函数分析 功能：在给定的数组 a 中，找到长度至少为 c 且密度最大的子数组，返回其密度，并记录子数组的起始位置 st 和结束位置 ed。

实现步骤： 初始化变量 s 用于记录当前子数组的元素和，ii 用于辅助，res 用于记录最大密度，q 是一个队列。 先将前 c 个元素加入队列，并计算它们的和 s 以及初始密度 res，同时记录子数组的起始和结束位置。 从第 c 个元素开始遍历数组，每次将新元素 t 加入队列，更新元素和 s。 如果当前子数组密度大于 res，则更新 res 和子数组的起始和结束位置。 如果队列长度大于等于 c 且队首元素小于等于当前元素 t，则不断弹出队首元素，更新元素和 s，如果弹出后子数组密度大于 res，则更新 res 和子数组的起始和结束位置。

#include<iostream>
#include<queue>
using namespace std;

int m,n,r,c;
int a[250][250], sum[250][250];

double getmost(int *a, int len, int lines, int &st, int &ed){
    int s = 0, ii = 0;
    double res;
    queue<int> q;
    for(int i =0; i < c; i++)
            res+=a[i], s+=a[i], q.push(a[i]);
    
    res = s/(c*lines*1.0);
    st = 0, ed = c-1;
    for(int i = c; i < len; i++){
            int t = a[i];
            q.push(a[i]);
            int l = q.size();
            s+=t;
            if(s/(lines*l*1.0)>res)
                             res = s/(lines*l*1.0), st = i-l+1, ed = i;
            while(q.size()>=c&&t>=q.front()){
                                             s-=q.front();
                                             l--;
                                             q.pop();
                                             if(s/(lines*l*1.0)>res)
                                                              res = s/(lines*l*1.0), st = i-l+1, ed = i;
            }
    }
    return res;
}
    

int main(){
    while(cin>>m&&m){
                     cin >> n >> r  >> c;
                     for(int i = 0; i < m; i++)
                             for(int j = 0; j < n; j++)
                                     cin >> a[i][j];
                     for(int i = 0; i < n; i++)
                             sum[0][i]=  a[0][i];
                     for(int i = 1; i < m; i++)
                             for(int j = 0; j < n; j++)
                                     sum[i][j] = a[i][j]+sum[i-1][j];
                     double res = 0;
                     int str, stc, edr, edc;
                     for(int baseline = 0; baseline+r-1<m; baseline++){
                             if(baseline>0){
                                            for(int i = baseline; i < m; i++)
                                                    for(int j = 0; j < n; j++)
                                                            sum[i][j]-=a[baseline-1][j];
                             }
                             int st,ed;
                             for(int endline = baseline+r-1; endline<m; endline++){
                                     double t = getmost(sum[endline],n,endline-baseline+1,st,ed);
                                     //cout <<baseline << ' ' << endline << ' ' << st << ' ' << ed << ' '<<t << endl;
                                     if(res<t){
                                               res = t;
                                               str = baseline, stc = st, edr = endline, edc = ed;
                                     }
                             }
                     }
                     cout << str+1 << ' ' << stc+1 << ' '  << edr+1 << ' '<< edc+1 << endl;
           }
           cout << '*' << endl;
}