在 C++ 中查找所有元素都相等的最大正方形子矩阵

在这个问题中，我们给定一个 N*N 矩阵 mat[]。我们的任务是查找所有元素都相等的最大的正方形子矩阵。

在这个问题中，我们需要从给定的矩阵中找到所有元素都相同的最大子矩阵的大小。

让我们举个例子来理解这个问题，

Input: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
Output: 2

解释 -

matrix a11, a12, a21, a22 is of size 2X2 and forms a sub-matrix with all equal elements.

解决方案方法

解决该问题的一个简单方法是遍历矩阵的所有元素，然后检查所有具有相同元素的子矩阵。算法的时间复杂度为 O(n3)，每个子矩阵的创建时间复杂度为 O(n2)。

另一种解决该问题的方法是使用动态规划，其中我们将存储每个位置之前所有元素都相同的最大子矩阵的大小。为此，我们将考虑相邻元素，然后考虑满足给定条件的最长矩阵。让我们制定 DP 矩阵的任何单元格的宽度。

如果所有元素的邻居都相同，我们将增加最长子矩阵的值。在这种情况下，

$DP[i][j]\: =\: min(DP[i-1][j] , DP[i][j-1], DP[i-1][j-1]) + 1$

如果不是这种情况，

DP[i][j] = 1

示例

程序说明我们解决方案的工作原理

#include<bits/stdc++.h>
#define n 4
#define m 4
using namespace std;
int findmaxSqMatSize(int mat[][m]){
   int DP[n][m];
   memset(DP, sizeof(DP), 0);
   int maxSqMatSize = 0;
   for (int i = 0 ; i < n ; i++){
      for (int j = 0 ; j < m ; j++){
         if (i == 0 || j == 0)
            DP[i][j] = 1;
         else{
            if (mat[i][j] == mat[i-1][j] && mat[i][j] == mat[i][j-1] && mat[i][j] == mat[i-1][j-1] )
               DP[i][j] = min(min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1] ) + 1;
            else DP[i][j] = 1;
         }
         maxSqMatSize = max(maxSqMatSize, DP[i][j]);
      }
   }
   return maxSqMatSize;
}
int main(){
   int mat[n][m] = { {2, 1, 4, 3},
   {5, 1, 1, 7},
   {1, 1, 1, 4},
   {9, 4, 6, 0}};
   cout<<"The maximum square sub-matrix with all equal elements is "<<findmaxSqMatSize(mat);
   return 0;
}

输出

The maximum square sub-matrix with all equal elements is 2

更新于: 2022-02-01

404 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告