数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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 次浏览
广告