最大的子方阵（martix）

Question

最大的子方阵（martix）（c++代码）
输入一个mn的矩阵（4<=m,n<=50），它是含有大小pq的子矩阵，（2<=p,q<=m,n），请找出mn矩阵和最大的pq子矩阵。

如下样例所示，对于以下为4*5的矩阵：

1 2 3 4 5

5 100 3 2 1

6 7 8 9 10

10 9 8 7 6

其最大的2*3的子矩阵：

5 100 3

6 7 8

输入格式
第一行，4个整数m，n，p，q

接下来共m行，每行有n个非负整数；

输出格式
共1行，空格隔开的三个数。分别为最大的p*q子矩阵的和（数据保证和在int范围内），以及其子矩阵的最左上角元素的横坐标、纵坐标。

输入/输出例子1
输入：

4 5 2 3

1 2 3 4 5

5 100 3 2 1

6 7 8 9 10

10 9 8 7 6

输出：

129 2 1

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

这个问题可以通过遍历矩阵的每个可能的子矩阵来解决。具体步骤如下：

1. 首先，读取输入的矩阵以及子矩阵的大小。
2. 然后，遍历矩阵中所有可能的子矩阵，并计算它们的和。
3. 在计算过程中，记录下最大子矩阵的和以及其左上角元素的坐标。
4. 最后，输出最大子矩阵的和以及其左上角元素的坐标。
   下面是一个可能的C++解决方案：
   cppCopy code

   #include <iostream>
   #include <vector>
   using namespace std;
   int main() {
   int m, n, p, q;
   cin >> m >> n >> p >> q;
   vector<vector<int>> matrix(m, vector<int>(n));
   // 读取矩阵
   for (int i = 0; i < m; ++i) {
   for (int j = 0; j < n; ++j) {
   cin >> matrix[i][j];
   }
   }
   int maxSum = 0;
   int maxSumRow = -1;
   int maxSumCol = -1;
   // 遍历所有可能的子矩阵
   for (int i = 0; i <= m - p; ++i) {
   for (int j = 0; j <= n - q; ++j) {
   int sum = 0;
   // 计算当前子矩阵的和
   for (int x = i; x < i + p; ++x) {
   for (int y = j; y < j + q; ++y) {
   sum += matrix[x][y];
   }
   }
   // 如果当前和大于之前记录的最大和，则更新最大和及其坐标
   if (sum > maxSum) {
   maxSum = sum;
   maxSumRow = i;
   maxSumCol = j;
   }
   }
   }
   // 输出结果
   cout << maxSum << " " << maxSumRow << " " << maxSumCol << endl;
   return 0;
   }
   

   这个代码首先读取输入的矩阵及子矩阵的大小，然后遍历所有可能的子矩阵，并计算它们的和。在计算过程中，记录下最大子矩阵的和以及其左上角元素的坐标。最后输出结果。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑