Problem

Given an $m \times n$ binary matrix, count the total number of square submatrices whose cells are all 1.

A square submatrix is a contiguous submatrix with equal height and width. Every square of every valid size should be counted separately.

Return the total count of such square submatrices.

Intuition

You need to count all-ones squares of size $1 \times 1$, $2 \times 2$, $3 \times 3$, and so on, anywhere in the matrix.

Input Format

• A binary matrix matrix of size m x n, where each cell is 0 or 1.

Output Format

• Return an integer: the number of square submatrices consisting entirely of 1s.

Constraints

• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1

Hints

• Think about the largest all-ones square that can end at each cell.
• If a cell is 1, its contribution depends on the neighboring subproblems above, left, and diagonally above-left.