We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Contain Virus

Difficulty: Hard

Problem Description

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 can be installed between any two 4-directionally adjacent cells, on the shared boundary. Each day, you can install walls around only one region that threatens the most uninfected cells the following night. 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.

Key Insights

  • Contaminated regions must be identified and quantified based on their potential threat to uninfected cells.
  • Walls can only be built around one region per day, targeting the most threatening one.
  • The spread of the virus must be simulated after each day of wall installation.
  • The algorithm involves a breadth-first search (BFS) or depth-first search (DFS) to explore regions and their boundaries.

Space and Time Complexity

Time Complexity: O(m * n) - Each cell is processed a limited number of times. Space Complexity: O(m * n) - For storing visited states and potentially the queue for BFS.

Solution

To solve the problem, we can use a breadth-first search (BFS) or depth-first search (DFS) to explore the infected regions. We will:

  1. Traverse the grid to identify all infected regions using BFS/DFS.
  2. For each infected region, calculate the number of walls needed to quarantine it and the number of uninfected cells it threatens.
  3. Select the region that threatens the most uninfected cells to quarantine.
  4. Install walls around that region and simulate the virus spreading to adjacent cells.
  5. Repeat the process until no infected regions remain or the entire grid is infected.

Code Solutions

def containVirus(isInfected):
    def dfs(x, y):
        stack = [(x, y)]
        area = 0
        walls = 0
        threat = 0
        visited.add((x, y))
        infected_cells = set()
        
        while stack:
            cx, cy = stack.pop()
            area += 1
            infected_cells.add((cx, cy))
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < len(isInfected) and 0 <= ny < len(isInfected[0]):
                    if isInfected[nx][ny] == 1 and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        stack.append((nx, ny))
                    elif isInfected[nx][ny] == 0:
                        walls += 1
                        threat += 1
        
        return area, walls, threat, infected_cells

    total_walls = 0
    while True:
        visited = set()
        regions = []
        for i in range(len(isInfected)):
            for j in range(len(isInfected[0])):
                if isInfected[i][j] == 1 and (i, j) not in visited:
                    region_info = dfs(i, j)
                    regions.append(region_info)

        if not regions:
            break

        # Find the region that threatens the most uninfected cells
        regions.sort(key=lambda x: -x[2])
        max_threat_region = regions[0]
        total_walls += max_threat_region[1]

        # Quarantine the most threatening region
        for r in range(len(regions)):
            for (x, y) in regions[r][3]:
                isInfected[x][y] = -1  # Mark quarantined
            if r > 0:  # Spread the other regions
                for (x, y) in regions[r][3]:
                    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < len(isInfected) and 0 <= ny < len(isInfected[0]):
                            if isInfected[nx][ny] == 0:
                                isInfected[nx][ny] = 1  # Spread the virus

    return total_walls
← Back to All Questions