C++程序：查找给定矩阵中 kxk 大小的相同值方阵

假设我们有一个二维矩阵，我们需要找到其中所有元素都相同值的最大 kxk 子矩阵，然后找到 k 的值。

例如，如果输入如下：

则输出为 3，因为存在一个 3x3 的值为 5 的方阵。

为了解决这个问题，我们将遵循以下步骤：

• n := 矩阵的行数

• m := 矩阵的列数

• 定义一个大小为 (nxm) 的二维数组 dp 并将其填充为 1

• ret := 1

• 初始化 i := n - 1，当 i >= 0 时，更新 (i 减 1)，执行：

  • 初始化 j := m - 1，当 j >= 0 时，更新 (j 减 1)，执行：

    • val := inf

    • 如果 i + 1 < n 且 v[i + 1, j] 与 v[i, j] 相同，则：

      • val := dp[i + 1, j] 和 val 的最小值

    • 否则

      • val := 0

    • 如果 j + 1 < m 且 v[i, j + 1] 与 v[i, j] 相同，则：

      • val := dp[i, j + 1] 和 val 的最小值

    • 否则

      • val := 0

    • 如果 i + 1 < n 且 j + 1 < m 且 v[i + 1, j + 1] 与 v[i, j] 相同，则：

      • val := dp[i + 1, j + 1] 和 val 的最小值

    • 否则

      • val := 0

    • 如果 val 等于 inf，则：

      • 忽略以下部分，跳到下一个迭代

    • dp[i, j] := dp[i, j] + val

      • ret := ret 和 dp[i, j] 的最大值

• 返回 ret

示例

让我们来看下面的实现以更好地理解：

在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<vector<int>>& v) {
      int n = v.size();
      int m = v[0].size();
      vector<vector<int>> dp(n, vector<int>(m, 1));
      int ret = 1;
      for (int i = n - 1; i >= 0; i--) {
         for (int j = m - 1; j >= 0; j--) {
            int val = INT_MAX;
            if (i + 1 < n && v[i + 1][j] == v[i][j]) {
               val = min(dp[i + 1][j], val);
            }
            else {
               val = 0;
            }
            if (j + 1 < m && v[i][j + 1] == v[i][j]) {
               val = min(dp[i][j + 1], val);
            }
            else {
               val = 0;
            }
            if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == v[i][j]) {
               val = min(dp[i + 1][j + 1], val);
            }
            else {
               val = 0;
            }
            if (val == INT_MAX)
               continue;
               dp[i][j] += val;
               ret = max(ret, dp[i][j]);
            }
         }
         return ret;
      }
};
int solve(vector<vector<int>>& matrix) {
   return (new Solution())->solve(matrix);
}
int main(){
   vector<vector<int>> matrix = {
      {1, 1, 8, 3},
      {1, 5, 5, 5},
      {2, 5, 5, 5},
      {4, 5, 5, 5}
   };
   cout << solve(matrix);
}

输入

{ {1, 1, 8, 3}, {1, 5, 5, 5}, {2, 5, 5, 5}, {4, 5, 5,
5} };

输出

3

Arnab Chakraborty

更新于：2020-12-23

浏览量：121

开启您的职业生涯

完成课程获得认证

开始学习