Show problems as
Classic problem #749HardArrayDepth-First SearchBreadth-First SearchMatrixSimulation

Contain Virus

Real-world version: Sealing Off the Mould
Tracked in this browser only
Read Contain Virus on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A basement floor plan is the grid isInfected, where isInfected[i][j] is 1 when the square is already mouldy and 0 when it is still clean. Two mouldy squares belong to the same patch when they share an edge; squares touching only at a corner are in different patches.

A contractor works in rounds. In a round:

  1. For each patch, look at the clean squares that share an edge with it. Call these the squares that patch threatens, counted as distinct squares.
  2. If no patch threatens any clean square, the job is finished.
  3. Otherwise the contractor seals the patch that threatens the most distinct clean squares. Sealing means fitting a panel on every edge between a square of that patch and a clean square, so a clean square that touches the patch on two sides costs two panels. The outer wall of the plan is already solid, so edges on the boundary of the grid need no panel.
  4. Every patch that was not sealed this round then grows: each clean square sharing an edge with such a patch becomes mouldy.

A sealed patch is finished with: it never grows again, and it is never sealed again. A patch that threatens no clean square is left as it is, since it cannot grow and needs no panel.

If two or more patches threaten the same number of distinct clean squares, seal the one whose first square comes earliest when the grid is read row by row, left to right within a row.

Return the total number of panels fitted once the job is finished.

Examples

Example 1

Input
isInfected = [[1, 1, 1, 1], [1, 0, 1, 0], [1, 1, 1, 1]]
Output
7

All the mouldy squares share edges, so they form one patch, which threatens the clean squares at (1, 1) and (1, 3). Square (1, 1) is touched on four sides and square (1, 3) on three, so sealing costs 7 panels and the job ends.

Example 2

Input
isInfected = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output
4

The single mouldy square threatens the four clean squares beside it and is sealed with one panel per shared edge, after which nothing can grow.

Example 3

Input
isInfected = [[1, 1], [1, 1]]
Output
0

The plan holds no clean square at all, so the one patch threatens nothing, no panel is fitted and the job is finished immediately.

Constraints

  • m == isInfected.length
  • n == isInfected[i].length
  • 1 <= m, n <= 50
  • isInfected[i][j] is either 0 or 1.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def contain_virus(isInfected: list[list[int]]) -> int:
Java
public int containVirus(int[][] isInfected)

More on the same topics