-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path221.maximal-square.cpp
More file actions
60 lines (55 loc) · 1.33 KB
/
221.maximal-square.cpp
File metadata and controls
60 lines (55 loc) · 1.33 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Tag: Array, Dynamic Programming, Matrix
// Time: O(MN)
// Space: O(MN)
// Ref: -
// Note: -
// 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.
//
// Example 1:
//
//
// Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
// Output: 4
//
// Example 2:
//
//
// Input: matrix = [["0","1"],["1","0"]]
// Output: 1
//
// Example 3:
//
// Input: matrix = [["0"]]
// Output: 0
//
//
// Constraints:
//
// m == matrix.length
// n == matrix[i].length
// 1 <= m, n <= 300
// matrix[i][j] is '0' or '1'.
//
//
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int d = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
d = max(d, dp[i][j]);
}
}
}
return d * d;
}
};