Участник:KislinskiyVadim/SubmatricesWithOnes

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
 
        m = len(matrix)
        n = len(matrix[0])
        dp_matrix = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
 
        answer = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == 1:
                    min_ = min(dp_matrix[i - 1][j - 1], dp_matrix[i][j - 1], dp_matrix[i - 1][j])
                    dp_matrix[i][j] = 1 + min_
                    answer += dp_matrix[i][j]
 
        return answer