1277. Count Square Submatrices with All Ones - medium
문제
Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
제한사항
- 1 <= arr.length <= 300
- 1 <= arr[0].length <= 300
- 0 <= arr[i][j] <= 1
입출력 예
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
Example 1:
Input: matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
Output: 15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
Output: 7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
풀이
- DP
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
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int count = 0;
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int>> result = vector<vector<int>>(m, vector<int>(n, 0));
for(auto i = 0 ; i < m ; ++i){
for(auto j = 0 ; j < n ; ++j){
// 가로, 세로 첫줄은 그대로 저장
if(i == 0 || j == 0){
result[i][j] = matrix[i][j];
}
// 0인 값은 그대로 0을 저장
else if(matrix[i][j] == 0){
result[i][j] = 0;
}
// 현재 index의 왼쪽, 위, 왼쪽 위 대각선, 이 세가지 값을 비교후 작은 값에 +1
// +1 하느 이유는 크기가 1인 사각형을 포함해야 하므로
else{
auto temp = min(matrix[i][j-1], result[i-1][j-1]);
result[i][j] = min(result[i-1][j], min(result[i][j-1], result[i-1][j-1])) + 1;
}
count += result[i][j];
}
}
return count;
}
};