547. Count the Rectangles of Ones

Count all rectangular submatrices consisting entirely of 1s, of every size including single cells.

1 1 1 1 -> 9 four singles, two horizontal pairs, two vertical pairs, one full

## Why problem 536's trick does not carry over

536 counts SQUARES by summing the per-cell table from 534, because the largest square ending at a cell determines how many squares end there: sides 1 through k, nested.

Rectangles are not nested that way. The rectangles ending at a cell have many widths and many heights, and no single number per cell determines how many there are.

So the count has to be built rather than read off.

## Count by bottom-right corner, walking up

Every rectangle has exactly one bottom-right corner, so grouping by it counts each once.

For a fixed corner (r, c), first compute the run of consecutive 1s ending at (r, c) along its row:

width[r][c] = number of consecutive 1s ending at (r, c) going left

Now walk UPWARD from row r, keeping the running minimum of width over the rows visited:

mn = width[r][c] for rr from r down to 0: mn = min(mn, width[rr][c]) if mn == 0: stop total += mn

## Why the running minimum is the count

A rectangle with bottom-right corner (r, c) and height h must have every one of its h rows extend at least as far left as its width. So the widest it can be is the MINIMUM of width over those h rows, and every width from 1 up to that minimum gives a distinct rectangle.

So each height contributes exactly the running minimum, and adding them as the walk goes up counts every rectangle with that corner.

Stopping when the minimum hits 0 is not just an optimisation: rows above a zero cannot contribute, and continuing would add nothing but would cost time.

## Cost

Time O(m n min(m, n)), since the upward walk is bounded by the number of rows. Space O(m n).

The full enumeration of every corner pair is O(m^2 n^2) and is worth stating first.

There is an O(m n) method using a monotonic stack per row, in the spirit of problem 535, and it is considerably harder to get right. Knowing it exists is enough.

## What the tests pin down

1 1 / 1 1 answers 9 and 1 1 1 / 1 1 1 / 1 1 1 answers 36. Both are small enough to count by hand, and 36 is the number of ways to choose two horizontal boundaries from four and two vertical boundaries from four, which is 6 * 6.

That closed form only holds for a completely filled grid, and checking it there is a good way to confirm the walk is not off by one.

1 0 1 / 0 1 0 / 1 0 1 answers 5, five isolated cells, which is the same answer as problem 536 gives on that grid because nothing larger than a single cell exists either way.

## Overflow

The count reaches roughly (m(m+1)/2)(n(n+1)/2), which at 200 by 200 is about 4 * 10^8. That fits in 32 bits but the running total is worth keeping in 64.

Constraints - `1 ≤ m ≤ 200` - `1 ≤ n ≤ 200` - every value is `0` or `1`