สี่เหลี่ยมจัตุรัสขนาดใหญ่ที่สุด (Maximal Square)
ให้เมทริกซ์ 2D บाइनนารี (0 และ 1) หาสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดที่ประกอบด้วย 1 เท่านั้น คืนค่าพื้นที่ (area)
ตัวอย่าง: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 → พื้นที่ 4 (สี่เหลี่ยม 2x2)
ขั้นตอนการแก้ปัญหา (Dynamic Programming)
- สร้าง DP table
dpขนาดเท่าเมทริกซ์ dp[i][j]= ความยาวด้านของสี่เหลี่ยมจัตุรัสที่ใหญ่ที่สุดซ้ายมุมขวาบนอยู่ที่(i,j)- สัมพันธ์: ถ้า
matrix[i][j] == '1':dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
- ติดตาม
maxSideระหว่างคำนวณ - คืนค่า
maxSide * maxSide
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int n = matrix.size(), m = matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
int maxSide = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) dp[i][j] = 1;
else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
};
อินพุทและเอาต์พุทตัวอย่าง
Input: [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
