在C ++中找到给定矩阵的k×k值相等的k的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个二维矩阵，我们必须找到最大的k×k子矩阵，其中所有元素都包含相同的值，然后找到k的值。

所以，如果输入像

那么输出将为3，因为存在一个3×3方阵，值为5。

在线示例

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

#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

以上是 在C ++中找到给定矩阵的k×k值相等的k的程序 的全部内容， 来源链接： utcz.com/z/315927.html