1277. Count Square Submatrices with All Ones
给一个m*n的矩阵
请回传这个矩阵有几个正方形(所有元素都是1)
思路:
用DP
dp[i][j]表示右下角为matrix[i][j]的正方形个数
当matrix[i][j]==1时
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
这样就可以计算出有几个正方型了
golang code :
func countSquares(matrix [][]int) int {
ans := 0
n, m := len(matrix), len(matrix[0])
for i := 0; i < n; i++ {
ans += matrix[i][0]
}
for i := 1; i < m; i++ {
ans += matrix[0][i]
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
if matrix[i][j] == 1 {
length := min(matrix[i-1][j], matrix[i][j-1])
length = min(length, matrix[i-1][j-1])
ans += length + 1
matrix[i][j] = length + 1
}
}
}
return ans
}