資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告