Count All-One Square Submatrices

Problem Statement

Given an m x n binary matrix grid containing only 0s and 1s, return the total number of square submatrices that are composed entirely of 1s.

A square submatrix is defined by choosing a top-left corner (r1, c1) and a bottom-right corner (r2, c2) such that r2 - r1 == c2 - c1.

Function Signature

def count_squares(grid: list[list[int]]) -> int:
    pass

Input & Output Format

• Input: A 2D list of integers grid of dimensions m x n, where each element is either 0 or 1.
• Output: An integer representing the total count of square submatrices containing only 1s.

Constraints

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

Examples

Example 1

Input:
grid = [
  [0, 1, 1, 1],
  [1, 1, 1, 1],
  [0, 1, 1, 1]
]
Output: 15
Explanation:
- 1x1 squares: 10
- 2x2 squares: 4
- 3x3 squares: 1
Total squares = 10 + 4 + 1 = 15.

Example 2

Input:
grid = [
  [1, 0, 1],
  [1, 1, 0],
  [1, 1, 0]
]
Output: 7
Explanation:
- 1x1 squares: 6
- 2x2 squares: 1
Total squares = 6 + 1 = 7.

Edge Cases

• Matrix with dimensions 1 x 1 (returns 1 if grid[0][0] == 1, else 0).
• Matrix consisting solely of 0s (returns 0).
• Matrix consisting solely of 1s.
• Single-row or single-column matrices.