Contain Virus
A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.
The world is modeled as an m x n binary grid isInfected, where isInfected[i][j] == 0 represents uninfected cells, and isInfected[i][j] == 1 represents cells contaminated with the virus. A wall, and only one wall, can be installed between any two 4-directionally adjacent cells on their shared boundary.
Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited: each day, you can install walls around only one region, meaning the affected area, a continuous block of infected cells, that threatens the most uninfected cells the following night. There will never be a tie.
Return the number of walls used to quarantine all the infected regions. If the world will become fully infected, return the number of walls used.
0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
isInfected = [[0,1,0,0,0,0,0,1],[0,1,0,0,0,0,0,1],[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0]]101 1 1 1 0 1 1 1 1
isInfected = [[1,1,1],[1,0,1],[1,1,1]]4Constraints
- m == isInfected.length
- n == isInfected[i].length
- 1 <= m, n <= 50
- isInfected[i][j] is either 0 or 1.
- There is always a contiguous viral region throughout the described process that will infect strictly more uncontaminated squares in the next round.