Counting Every Square of Ones
A grid holds 0s and 1s. Count every all-ones square submatrix it contains, of
every size, and print that count. Two squares are different if they sit in different
places, so squares of different sizes at the same corner all count separately.
1 1 1
1 1 1 -> 14
1 1 1
There are nine squares of side 1, four of side 2, and one of side 3, and 9 + 4 + 1 = 14.
1 1 0
1 1 0 -> 6 five of side 1, one of side 2
0 0 1
1 0 1
0 1 0 -> 5 no two ones touch, so only the five single cells
1 0 1
## What most people try first
Enumerate the squares directly: pick a top-left corner, pick a side, and check every cell inside. At 300 by 300 there are 9,045,050 candidate squares, and verifying each one fully costs 82,359,030,040 cell reads. That is roughly nine hundred thousand times the work of the table below, and it does not finish.
A partial repair is to stop checking a square as soon as a zero appears. That helps on sparse grids and does nothing on the dense ones, which are exactly the grids with the most squares to count.
## The table
``` dp[r][c] = the side of the largest all-ones square whose BOTTOM-RIGHT corner is (r, c)
g[r][c] == 0 -> dp[r][c] = 0 otherwise -> dp[r][c] = 1 + min( dp[r-1][c], dp[r][c-1], dp[r-1][c-1] )
answer = sum of dp over every cell ```
## Why the sum is the count
This is the whole problem, and it is worth proving rather than believing.
Fix a cell (r, c) and let dp[r][c] = s. For each k from 1 to s there is exactly
ONE square of side k with its bottom-right corner there, namely the one covering rows
r-k+1 .. r and columns c-k+1 .. c. Each of those sits inside the square of side s,
so each is all ones. And no square of side greater than s ends there, by the definition
of dp. So the number of all-ones squares with bottom-right corner (r, c) is exactly
s.
Every all-ones square has exactly one bottom-right cell, so summing s over all cells
counts each square once and never twice. That is why a single pass with no extra bookkeeping
gets the count.
## Why the recurrence takes a minimum of three
A square of side k ending at (r, c) needs a square of side k-1 ending directly above,
one ending directly left, AND one ending diagonally up-left. Any one of the three being
smaller caps the result, so the side is limited by the SMALLEST.
The diagonal neighbour is the one people leave out. Dropping it does not always change the
answer, which is what makes the bug survive casual testing: on 1 1 0 / 1 1 0 / 0 0 1 a
two-neighbour version still answers 6. The grid that exposes it is 0 1 1 / 1 1 1 / 1 1 1,
where the single zero sits in the top-left corner. There the two-neighbour version answers
13 against the true 11, because it claims a side-2 square ending at the centre and a side-3
square ending at the bottom-right corner, and neither of those is solid.
## The borders
Row 0 and column 0 have no upper or left neighbour, so dp there is just the cell value.
Writing the general formula for those cells reads out of bounds. Pad the table with a row
and a column of zeros and the special case disappears.
## The magnitude
The count is largest when the grid is entirely ones, and then it is
1^2 + 2^2 + ... + 300^2 = 9,045,050. That is comfortably under 2147483647, so a
32-bit accumulator is enough here. Compute that bound rather than assume it: the same
question asked for RECTANGLES instead of squares grows much faster.
## Cost
Time O(m n). Space O(m n), reducible to O(n) with two rows.
Problem 436 builds the identical table and takes the MAXIMUM entry, then squares it, to get the area of the single largest square. Same table, different reduction: max answers "how big is the best one", sum answers "how many are there". On the 4 by 5 grid in the tests, 436 answers 4 and this problem answers 15.