[LeetCode]Contain Virus


LeetCode 749. Contain Virus

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the 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 -- the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: grid = 
Output: 10
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:


On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = 
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 3:

Input: grid = 
Output: 13
Explanation: The region on the left only builds two new walls.


  1. The number of rows and columns of grid will each be in the range [1, 50].
  2. Each grid[i][j] will be either 0 or 1.
  3. Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.








class Solution(object):
    def containVirus(self, grid):
        :type grid: List[List[int]]
        :rtype: int
        m, n = len(grid), len(grid[0])
        stop = False
        allCellWalls = collections.defaultdict(set)
        while not stop:
            stop = True
            quarantineNeighbors = dict()
            surroundedViruses = set()
            visitedCells = set()
            affectedCells = set()
            for x in range(m):
                for y in range(n):
                    if grid[x][y] > 0 and (x, y) not in visitedCells:
                        stop = False
                        cellWalls, virusCells = self.cellWalls(grid, x, y, m, n)
                        if not quarantineNeighbors or len(cellWalls.keys()) > len(quarantineNeighbors.keys()):
                            quarantineNeighbors = cellWalls
                            surroundedViruses = virusCells
                        affectedCells |= set(cellWalls.keys())
                        visitedCells |= virusCells
            for key in quarantineNeighbors: allCellWalls[key] |= quarantineNeighbors[key]
            confirmInfectedCells = []
            for x, y in affectedCells:
                for idx, (dx, dy) in enumerate(zip([0, -1, 0, 1], [-1, 0, 1, 0])):
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < m and 0 <= ny < n:
                        if grid[nx][ny] > 0 and idx not in allCellWalls[(x, y)]:
                            confirmInfectedCells.append((x, y))
            for x, y in confirmInfectedCells: grid[x][y] = 1
            for x, y in surroundedViruses: grid[x][y] = -1
        return sum(len(v) for v in allCellWalls.values())

    def cellWalls(self, grid, x, y, m, n):
        queue = [[x, y]]
        cellWalls = collections.defaultdict(set)
        virusCells = set([(x, y)])
        walls = 0
        while queue:
            px, py = queue.pop(0)
            for idx, (dx, dy) in enumerate(zip([0, 1, 0, -1], [1, 0, -1, 0])):
                nx = px + dx
                ny = py + dy
                if 0 <= nx < m and 0 <= ny < n:
                    if grid[nx][ny] == 0:
                        cellWalls[(nx, ny)].add(idx)
                    elif (nx, ny) not in virusCells and grid[nx][ny] > 0:
                        queue.append((nx, ny))
                        virusCells.add((nx, ny))
        return cellWalls, virusCells



如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码