ในปัญหานี้ เราได้รับเมทริกซ์ N*N mat[] ภารกิจของเราคือ หา square sub-matrix สูงสุดที่มีองค์ประกอบเท่ากันทุกตัว
ในปัญหานี้ เราต้องหาขนาดสูงสุดของ sub-matrix จากเมทริกซ์ที่กำหนดซึ่งองค์ประกอบทั้งหมดเหมือนกัน
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: mat[][] = {{1, 2, 1}, {1, 2, 2}, {2, 2, 2}} Output: 2
คำอธิบาย -
เมทริกซ์ a11, a12, a21, a22 เป็นขนาด 2X2 และเป็น sub-matrix ที่มีองค์ประกอบเท่ากันทุกตัว
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการเดินทางผ่านทุกองค์ประกอบของเมทริกซ์แล้วตรวจสอบ sub-matrices ทั้งหมดที่มีองค์ประกอบเดียวกัน ความซับซ้อนของอัลกอริทึมคือ O(n3) และแต่ละ sub-matrix สร้างด้วยความซับซ้อน O(n2)
วิธีทางเลือก ในการแก้ปัญหาคือการใช้ dynamic programming ที่เราจะเก็บขนาดใหญ่ที่สุดของ sub-matrix ที่มีองค์ประกอบเท่ากันทุกตัวจนถึงตำแหน่วนั้น สำหรับนี้ เราจะพิจารณาองค์ประกอบเพื่อนบนแล้วพิจารณาเมทริกซ์ที่ยาวที่สุดที่ตรงตามเงื่อนไข ให้เรากำหนดความกว้างของเซลล์ใดๆ ของเมทริกซ์ DP
ถ้าเพื่อนบนทั้งหมดขององค์ประกอบเหมือนกัน เราจะเพิ่มค่าของ sub-matrix ที่ยาวที่สุด ในกรณีนี้,
$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
