441. Count Every Square of Ones
A grid holds 0s and 1s. Count ALL all-ones squares of every size, counting
squares at different positions separately.
0 1 1 1
1 1 1 1 -> 15
0 1 1 1
Problem 436 finds the LARGEST such square. This counts them all, and the table is identical: only what you do with the entries changes.
side[i][j] = 0 if grid[i][j] == 0
= 1 + min(side[i-1][j], side[i][j-1], side[i-1][j-1]) otherwise
The step worth understanding is why the ANSWER is the sum of every entry.
side[i][j] = k means there is an all-ones square of side k ending at that cell,
and therefore also one of side k-1, k-2 and so on down to 1, all ending at the
same cell. That is exactly k squares whose bottom-right corner is (i, j). Every
square has exactly one bottom-right corner, so summing the entries counts each
square once and none twice.
436 takes the maximum of the same table and squares it. Recognising that one table answers both questions is the point of putting them next to each other.
Constraints - `1 ≤ r, c ≤ 300` - Every value is `0` or `1`.
Input
The first line contains two integers r and c.
Each of the next r lines contains c space-separated values, each 0 or 1.
Output
Print how many all-ones squares the grid contains, of all sizes.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.