FunctionRacerProblemsRace

Wall Off the Outbreak

HardGridsPython, JavaScript, TypeScript, Java, C++

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

grid [[0,1,0,0],[0,0,0,1]]
returns 6

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

grid [[1,0,0]]
returns 1

One wall between the infected cell and its only healthy neighbor.

Example 3

grid [[1,1],[1,1]]
returns 0

Nothing is healthy, so nothing needs a wall.

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 Grids problems