-
Notifications
You must be signed in to change notification settings - Fork 2
/
Maximal Square
31 lines (27 loc) · 937 Bytes
/
Maximal Square
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.empty()) return 0;
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m,vector<int>(n));
//top row.
for(int j = 0;j<n;j++) dp[0][j] = matrix[0][j]-'0';
//left column;
for(int i = 0;i<m;i++) dp[i][0] = matrix[i][0]-'0';
for(int i = 1;i<m;i++)
for(int j = 1;j<n;j++)
{
if(matrix[i][j]-'0' == 1)
dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
int square_lenth = INT_MIN;
for(int i = 0;i<m;i++)
for(int j = 0;j<n;j++)
{
if(dp[i][j]>square_lenth) square_lenth = dp[i][j];
}
cout << square_lenth <<endl;
return square_lenth*square_lenth;
}
};