LeetCode 题解工作台
隔离病毒
病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。 假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 表示该区域未感染病毒，而 isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 2 个相邻单元之间的…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
DFS 找到每个病毒区域 `areas[i]`，同时记录每个区域边界节点 `boundaries[i]` 以及周长 `c[i]`。 接着对威胁最大的病毒区域进行隔离，累加所需的防火墙数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 表示该区域未感染病毒，而 isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。
每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。
你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。
示例 1：
输入: isInfected = [[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]] 输出: 10 解释:一共有两块被病毒感染的区域。 在第一天，添加 5 墙隔离病毒区域的左侧。病毒传播后的状态是:第二天，在右侧添加 5 个墙来隔离病毒区域。此时病毒已经被完全控制住了。
示例 2：
输入: isInfected = [[1,1,1],[1,0,1],[1,1,1]] 输出: 4 解释: 虽然只保存了一个小区域，但却有四面墙。 注意，防火墙只建立在两个不同区域的共享边界上。
示例 3:
输入: isInfected = [[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]] 输出: 13 解释: 在隔离右边感染区域后，隔离左边病毒区域只需要 2 个防火墙。
提示:
m == isInfected.lengthn == isInfected[i].length1 <= m, n <= 50isInfected[i][j]is either0or1- 在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮 严格地感染更多未受污染的方块
解题思路
方法一：DFS 暴力模拟
DFS 找到每个病毒区域 areas[i]，同时记录每个区域边界节点 boundaries[i] 以及周长 c[i]。
接着对威胁最大的病毒区域进行隔离，累加所需的防火墙数量。
剩余的病毒区域向外感染一个区域。
class Solution:
def containVirus(self, isInfected: List[List[int]]) -> int:
def dfs(i, j):
vis[i][j] = True
areas[-1].append((i, j))
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if isInfected[x][y] == 1 and not vis[x][y]:
dfs(x, y)
elif isInfected[x][y] == 0:
c[-1] += 1
boundaries[-1].add((x, y))
m, n = len(isInfected), len(isInfected[0])
ans = 0
while 1:
vis = [[False] * n for _ in range(m)]
areas = []
c = []
boundaries = []
for i, row in enumerate(isInfected):
for j, v in enumerate(row):
if v == 1 and not vis[i][j]:
areas.append([])
boundaries.append(set())
c.append(0)
dfs(i, j)
if not areas:
break
idx = boundaries.index(max(boundaries, key=len))
ans += c[idx]
for k, area in enumerate(areas):
if k == idx:
for i, j in area:
isInfected[i][j] = -1
else:
for i, j in area:
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:
isInfected[x][y] = 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates a strong understanding of DFS and its application to this problem.
- question_mark
The ability to identify and prioritize the most threatening viral regions indicates an efficient solution approach.
- question_mark
Clear understanding of how to simulate the virus spread and use walls to contain it will be crucial.
常见陷阱
外企场景- error
Failing to track the boundaries of infected regions properly can lead to incorrect wall placement.
- error
Not correctly assessing which viral region will spread the most can result in inefficient containment.
- error
Over-complicating the algorithm without optimizing the DFS can lead to performance issues on larger grids.
进阶变体
外企场景- arrow_right_alt
Consider adding additional constraints, such as limiting the number of walls that can be placed.
- arrow_right_alt
Modify the problem to allow walls to be built in multiple regions simultaneously.
- arrow_right_alt
Implement the solution using a Breadth-First Search (BFS) approach instead of DFS to compare performance and efficiency.