Wall Off the Outbreak
grid shows an outbreak: 1 is an infected cell and 0 is a healthy one. Infected cells that touch side by side form a region.
Every night two things happen, in this order:
1. Take the region with the most healthy cells next to it, counting each healthy cell once. On a tie, take the region whose first cell in reading order (top row first, left to right) comes first. Seal it: build one wall on every side where a cell of the region touches a healthy cell. A sealed region never spreads again.
2. Every other region that is not sealed infects all the healthy cells next to it.
This goes on until no unsealed region has a healthy cell next to it. Return the number of walls built.
Example 1
Night 1: the top region has 3 healthy cells next to it and is sealed with 3 walls, while the other one grows to 3 cells. Night 2: sealing that one takes 3 more walls.
Example 2
One wall between the infected cell and its only healthy neighbor.
Example 3
Nothing is healthy, so nothing needs a wall.
Constraints
1 <= len(grid) <= 10and1 <= len(grid[0]) <= 10- every cell is 0 or 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Grids problems
- Water Held by the LandHard
- Column TotalsBeginner
- Count Negatives in a Sorted GridBeginner
- Cross TotalBeginner
- Enlarge the PictureBeginner
- Frame TotalBeginner
- Heaviest RowBeginner
- Layer LabelsBeginner