ในปัญหานี้ เราได้รับเมทริกซ์เมทริกซ์ N*N[] งานของเราคือ การหาเมทริกซ์ย่อยกำลังสองสูงสุดที่มีองค์ประกอบเท่ากันทั้งหมด .
ในปัญหานี้ เราจำเป็นต้องค้นหาขนาดสูงสุดของเมทริกซ์ย่อยจากเมทริกซ์ที่กำหนดซึ่งมีองค์ประกอบทั้งหมดเหมือนกัน
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
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(n 3 ) และเมทริกซ์ย่อยแต่ละรายการถูกสร้างขึ้นด้วยความซับซ้อนของเวลาของ O(n 2 )
วิธีทางเลือก เพื่อแก้ปัญหาโดยใช้ ไดนามิกการเขียนโปรแกรม โดยเราจะเก็บขนาดที่ใหญ่ที่สุดของเมทริกซ์ย่อยที่มีองค์ประกอบทั้งหมดจนถึงตำแหน่ง สำหรับสิ่งนี้ เราจะพิจารณาองค์ประกอบที่อยู่ใกล้เคียง จากนั้นจึงพิจารณาเมทริกซ์ที่ยาวที่สุดที่ตรงตามเงื่อนไขที่กำหนด มากำหนดความกว้างของเซลล์ใดๆ ของเมทริกซ์ 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
