FunctionRacerProblemsRace

Count the Free Plots

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems