0563HardArrayDepth-First SearchBreadth-First SearchMatrixSimulation

Sealing Off the Mould

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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:

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.
If no patch threatens any clean square, the job is finished.
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.
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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def contain_virus(isInfected: list[list[int]]) -> int:

Java

public int containVirus(int[][] isInfected)

The intended approach

Time O(rounds * m * n); each round is a constant number of passes over the plan.Space O(m * n) for the working plan, the visited flags and the patch data.

Keep a working copy of the plan with three states per square: clean, mouldy and sealed. Each round, flood fill from every unvisited mouldy square using an explicit stack, collecting the patch's squares, the set of distinct clean squares it touches, and a separate count of touching edges, which is larger whenever a clean square is touched from more than one side. Because the scan is row by row, the patch discovered first is also the one whose earliest square comes first, so the tie-break falls out of a strict comparison while picking the maximum. Add the chosen patch's edge count to the running total, mark its squares sealed, and then convert the touched squares of every other patch to mould. Stop when no patch touches a clean square.

Pythonentry point: contain_virus

def contain_virus(isInfected):
    # O(rounds * m * n) time, O(m * n) space. Each round: flood fill every live
    # region with an explicit stack (no recursion, so a 50x50 plan is safe),
    # measure how many distinct clean squares it touches and how many shared
    # edges it has, seal the worst one, then let the rest creep outward.
    grid = [row[:] for row in isInfected]
    m = len(grid)
    n = len(grid[0])
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    total = 0
    while True:
        seen = [[False] * n for _ in range(m)]
        regions = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1 or seen[i][j]:
                    continue
                stack = [(i, j)]
                seen[i][j] = True
                cells = []
                touched = set()
                panels = 0
                while stack:
                    r, c = stack.pop()
                    cells.append((r, c))
                    for dr, dc in steps:
                        nr = r + dr
                        nc = c + dc
                        if nr < 0 or nr >= m or nc < 0 or nc >= n:
                            continue
                        if grid[nr][nc] == 1:
                            if not seen[nr][nc]:
                                seen[nr][nc] = True
                                stack.append((nr, nc))
                        elif grid[nr][nc] == 0:
                            touched.add((nr, nc))
                            panels += 1
                regions.append({"threat": len(touched), "first": (i, j),
                                "cells": cells, "panels": panels,
                                "touched": touched})
        pick = -1
        for idx, reg in enumerate(regions):
            if reg["threat"] == 0:
                continue
            if pick < 0 or reg["threat"] > regions[pick]["threat"]:
                pick = idx
        if pick < 0:
            return total
        total += regions[pick]["panels"]
        for r, c in regions[pick]["cells"]:
            grid[r][c] = 2
        for idx, reg in enumerate(regions):
            if idx == pick:
                continue
            for r, c in reg["touched"]:
                grid[r][c] = 1

The obvious version

Identify patches without any traversal: give every mouldy square its own label, then repeatedly replace each label with the smallest label among its edge neighbours until nothing changes, which leaves one shared label per patch. Group the squares by label, measure each group by rescanning its squares, and run the same round structure.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_contain_virus(isInfected):
    grid = [row[:] for row in isInfected]
    m = len(grid)
    n = len(grid[0])
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    total = 0
    while True:
        label = {}
        nxt = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    label[(i, j)] = nxt
                    nxt += 1
        changed = True
        while changed:
            changed = False
            for (r, c) in list(label):
                for dr, dc in steps:
                    key = (r + dr, c + dc)
                    if key in label and label[key] < label[(r, c)]:
                        label[(r, c)] = label[key]
                        changed = True
        groups = {}
        for cell, lab in label.items():
            groups.setdefault(lab, []).append(cell)
        best = None
        for lab in sorted(groups):
            cells = sorted(groups[lab])
            touched = set()
            panels = 0
            for (r, c) in cells:
                for dr, dc in steps:
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 0:
                        touched.add((nr, nc))
                        panels += 1
            groups[lab] = (cells, touched, panels)
            if touched and (best is None or len(touched) > len(groups[best][1])
                            or (len(touched) == len(groups[best][1])
                                and cells[0] < groups[best][0][0])):
                best = lab
        if best is None:
            return total
        total += groups[best][2]
        for (r, c) in groups[best][0]:
            grid[r][c] = 2
        for lab in groups:
            if lab == best:
                continue
            for (r, c) in groups[lab][1]:
                grid[r][c] = 1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in