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
}