Trong bài toán này, chúng ta được đưa ra một ma trận N * N []. Nhiệm vụ của chúng tôi là tìm ma trận con vuông lớn nhất có tất cả các phần tử bằng nhau .
Trong bài toán này, chúng ta cần tìm kích thước lớn nhất của ma trận con từ ma trận đã cho mà tất cả các phần tử đều giống nhau.
Hãy lấy một ví dụ để hiểu vấn đề,
Input: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}}
Output: 2 Giải thích -
matrix a11, a12, a21, a22 is of size 2X2 and forms a sub-matrix with all equal elements.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là duyệt qua tất cả các phần tử của ma trận và sau đó kiểm tra tất cả các ma trận con có cùng phần tử. Độ phức tạp về thời gian của thuật toán là O (n 3 ) và mỗi ma trận con được tạo với độ phức tạp thời gian là O (n 2 ).
Phương pháp thay thế để giải quyết vấn đề bằng cách sử dụng lập trình động nơi chúng tôi sẽ lưu trữ kích thước lớn nhất của ma trận con với tất cả các phần tử cho đến vị trí. Đối với điều này, chúng tôi sẽ xem xét các phần tử lân cận và sau đó xem xét ma trận dài nhất thỏa mãn điều kiện cho trước. Hãy hình thành chiều rộng của bất kỳ ô nào trong ma trận DP.
Nếu tất cả các lân cận của các phần tử đều giống nhau, chúng ta sẽ tăng các giá trị của ma trận con dài nhất. Trong trường hợp này,
$ DP [i] [j] \:=\:min (DP [i-1] [j], DP [i] [j-1], DP [i-1] [j-1]) + 1 $
Nếu không phải như vậy,
DP [i] [j] =1
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The maximum square sub-matrix with all equal elements is 2