Count the Free Plots
land is a map given as a list of rows, where 0 is a free cell and 1 is a built-on cell. A plot is a square block of cells, of any size from 1 by 1 up, in which every cell is free.
Return the number of plots. Plots may overlap: a 2 by 2 block of free cells holds five plots, four of size 1 and one of size 2.
Example 1
land [[0,0,1],[0,0,0],[1,0,0]]
returns 9
Seven free cells give seven 1 by 1 plots, and there are two free 2 by 2 blocks: top left and bottom right.
Example 2
land [[1,1],[1,1]]
returns 0
Every cell is built on.
Constraints
1 <= len(land) <= 101 <= len(land[0]) <= 10, every row the same lengthland[r][c]is0or1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Dice Sum WaysMedium
- Fairest Stone SplitMedium
- Fewest Perfect SquaresMedium
- Gems That ClashMedium
- Hands That Hit the TargetMedium
- Keystrokes to TransformMedium
- Knight on the KeypadMedium
- Letter DecodingsMedium