推 DJYOMIYAHINA: 剩我還多開一個dp array了 10/27 18:36
→ dont: 開新的1d array比直接改matrix好吧 10/27 19:13
1277. Count Square Submatrices with All Ones
## 思路
DP
matrix[r][c] = 右下角為(r, c)的正方形個數
1 + min(matrix[r-1][c-1], matrix[r][c-1], matrix[r-1][c])
更新matrix並加總
## Code
```python
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
len_r, len_c = len(matrix), len(matrix[0])
res = 0
for r in range(len_r):
for c in range(len_c):
if r and c and matrix[r][c]:
matrix[r][c] = 1 + min(matrix[r-1][c-1], matrix[r-1][c],
matrix[r][c-1])
res += matrix[r][c]
return res
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.7 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730023302.A.781.html