#749
Contain Virus
candidate master · 1375 · lc hard +32 · verified · 54.4% accepted · 441 likes · top 47%
Description
A virus spreads across an m x n binary grid isInfected (0 = healthy, 1 = infected). Each night it expands 4-directionally unless blocked by walls you install. Each day you may wall off only the single contiguous infected region that threatens the most healthy cells that night (no ties). Walling a region prevents it from spreading further.
Return the total number of walls placed before the virus is fully contained (or the world is fully infected).
Example 1:
Input: 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]]
Output: 10
Explanation: There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:
Example 2:
On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.
Example 3:
Input: isInfected = [[1,1,1],[1,0,1],[1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.
Example 4:
Input: isInfected = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.
Code
1
2
3