Count Square Submatrices with All Ones
Medium · dynamic programming
A square courtyard is tiled with n rows and n columns of tiles. Each tile is either intact (1) or cracked (0).
Count the square blocks made only of intact tiles. A block is a square of any side length 1 or more, whose edges line up with the tile grid. Blocks of different sizes or at different positions are counted separately, so a single intact tile counts as one block, and a larger block also contains smaller blocks that count too.
Return the total number of such blocks.
Examples
Example 1
Input: tiles = [[1, 0, 1], [1, 1, 1], [0, 1, 1]]
Output: 8
There are 7 intact tiles, which give 7 blocks of side 1. The only block of side 2 is the one in the bottom-right corner, and no block of side 3 fits: 7 + 1 = 8.
Example 2
Input: tiles = [[1, 1], [1, 1]]
Output: 5
Four blocks of side 1 and one block of side 2.
Example 3
Input: tiles = [[0]]
Output: 0
A cracked tile forms no block.
Constraints
- 1 <= len(tiles) <= 100, and tiles has the same number of columns as rows.
- tiles[i][j] is 0 or 1.