← 返回 google 的题目列表Count Total Number (or Total Area) of Square Submatrices
类型：online_judge
Problem: Count All-Ones Square Submatrices
Given a binary matrix matrix of size m x n, compute the total number of square submatrices consisting of all 1s (counting squares of all side lengths).
Input
m n
m rows of n values (0/1), space-separated or as characters.
Output
An integer: the total count of all-ones square submatrices.
Constraints
1 <= m, n <= 1000
Example
Input:
2 2
1 1
1 1
Output:
5
Because there are four 1x1 squares and one 2x2 square.
Example
Input
2 2
1 1
1 1
Output
5