题目描述：
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 = [[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: [[0,1,0,0,0,0,1,1], [0,1,0,0,0,0,1,1], [0,0,0,0,0,0,1,1], [0,0,0,0,0,0,0,1]] On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.
Example 2:
Input: grid = [[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 3:
Input: grid = [[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.
Note:
- The number of rows and columns of
gridwill each be in the range[1, 50]. - Each
grid[i][j]will be either0or1. - Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.
题目描述：
二维矩阵grid表示一组细胞，1表示病毒感染的细胞，0表示正常细胞。
病毒感染的细胞会感染其邻近细胞，为防止病毒扩散，每一天在受影响最多的细胞周围设立“隔离墙”。
求最终会设立多少隔离墙。
解题思路：
BFS（广度优先搜索）
Python代码：
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))
break
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
本文链接：http://bookshadow.com/weblog/2017/12/17/leetcode-contain-virus/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
