Count Submatrices With All Ones LeetCode solution in Python

1
class Solution:
2
    def numSubmat(self, mat: List[List[int]]) -> int:
3
        from dataclasses import dataclass
4

5
        @dataclass
6
        class Cell:
7
            left: int = 0
8
            top: int = 0
9

10
        n = len(mat)
11
        m = len(mat[0])
12
        dp = [[Cell() for _ in range(m + 1)] for _ in range(n + 1)]
13

14
        ans = 0
15
        for i in range(1, n + 1):
16
            for j in range(1, m + 1):
17
                if mat[i - 1][j - 1]:
18
                    dp[i][j].top = 1 + dp[i - 1][j].top
19
                    dp[i][j].left = 1 + dp[i][j - 1].left
20

21
                    min_height = dp[i][j].top
22
                    for k in range(dp[i][j].left):
23
                        min_height = min(min_height, dp[i][j - k].top)
24
                        ans += min_height
25
        return ans