在 C++ 中查找所有元素都相等的最大方子矩阵
c++server side programmingprogramming更新于 2025/3/15 11:07:17
在此问题中，我们给定一个 N*N 矩阵 mat[]。我们的任务是找到所有元素都相等的最大方阵。
在这个问题中，我们需要从给定的矩阵中找出所有元素都相同的子矩阵的最大大小。
让我们举一个例子来理解这个问题，
输入：mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
输出：2
解释 −
矩阵 a11、a12、a21、a22 的大小为 2X2，并形成一个所有元素都相等的子矩阵。
解决方法
该问题的一个简单解决方案是遍历矩阵的所有元素，然后检查所有具有相同元素的子矩阵。该算法的时间复杂度为 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<<"所有元素相等的最大方阵子矩阵为 "<<findmaxSqMatSize(mat);
return 0;
}
输出
所有元素相等的最大方阵子矩阵为 2
