221. Maximal Square
Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int res = 0, n = matrix.size(), m = matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
for(int i = 0; i < max(m,n); i++) {
if(i < n)
for(int j = i; j < m; j++) {
if(matrix[i][j] != '1') continue;
if(!i || !j) dp[i][j] = matrix[i][j] & 0b1111;
else dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
res = max(dp[i][j], res);
}
if(i < m)
for(int j = i + 1; j < n; j++) {
if(matrix[j][i] != '1') continue;
if(!i || !j) dp[j][i] = matrix[j][i] & 0b1111;
else dp[j][i] = min(dp[j-1][i-1], min(dp[j-1][i], dp[j][i-1])) + 1;
res = max(dp[j][i], res);
}
}
return res * res;
}
};
|
