A flat roof is given as a list of equal-length strings roof, where '.' is a clear cell and
'#' is a vent. A rectangular tarp may be laid over any rectangle of whole cells (any height and
width of at least 1, lined up with the grid) as long as every cell under it is clear. Return
the number of different rectangles where a tarp can be laid.
Examples
Input: roof = ["..", ".."]
Output: 9
Explanation: four 1x1, two 1x2, two 2x1 and one 2x2 rectangle.
Input: roof = [".#.", "..."]
Output: 10
Explanation: five 1x1, two 1x2 and one 1x3 in the bottom row, and two 2x1 (columns 0 and 2).
Input: roof = ["#"]
Output: 0
Constraints
1 <= len(roof), len(roof[0]) <= 300- The largest tests are 300 x 300 roofs that are mostly clear; checking every rectangle, or every pair of columns for every row, is too slow.
Goals
- Turn each row into a skyline of open-cell heights
- Count rectangles by their bottom-right corner
- Use a stack of increasing heights to reuse earlier counts