1.题目基本信息
1.1.题目描述
病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 表示该区域未感染病毒，而 isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。
每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。
你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。
1.2.题目地址
https://leetcode.cn/problems/contain-virus/description/
2.解题方法
2.1.解题思路
广度优先搜索+贪心
2.2.解题步骤
第一步，构建一个死循环，直到没有没被隔离的连通分量
-
1.1.遍历矩阵，对于每个连通分量进行广搜，并给每个连通分量进行编号为idx，再记录每个连通分量需要的防火墙数量和邻居节点集合；并在搜索后将病毒感染位置的值设置为-(idx+1)，表示已经广搜过了（这样将标记和idx挂钩，方便后续的修改）
-
1.2.退出条件判断
-
1.3.找到邻居结点数最多的连通分量的maxIdx
-
1.4.将maxIdx对应的连通分量的节点全部设置为2，表示已经被防火墙隔离；将非maxIdx的连通分量的值标记为1，进行恢复，即将不等于-(maxIdx+1)且小于0的节点标记为1；并更新结果变量总防火墙数
-
1.5.将非maxIdx的连通分量的邻居结点标记为1，表示没被隔离的区域扩展一个单位
3.解题代码
python3代码
from collections import deque
class Solution:
def containVirus(self, isInfected: List[List[int]]) -> int:
# 思路：广度优先搜索+贪心。每次取下一步能感染的区域最多的连通分量建立防火墙
m, n = len(isInfected), len(isInfected[0])
# 第一步，构建一个死循环，直到没有没被隔离的连通分量
result = 0
while True:
# 1.1.遍历矩阵，对于每个连通分量进行广搜，并给每个连通分量进行编号为idx，再记录每个连通分量需要的防火墙数量和邻居节点集合；并在搜索后将病毒感染位置的值设置为-(idx+1)，表示已经广搜过了（这样将标记和idx挂钩，方便后续的修改）
idx = 0
firewares = []
neighbors = []
for i in range(m):
for j in range(n):
if isInfected[i][j] == 1:
que = deque([(i, j)])
isInfected[i][j] = -(idx + 1)
neighborSet = set()
fireware = 0
while que:
for _ in range(len(que)):
r, c = que.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n:
if isInfected[nr][nc] == 1:
que.append((nr, nc))
isInfected[nr][nc] = -(idx + 1)
elif isInfected[nr][nc] == 0:
fireware += 1
neighborSet.add((nr, nc))
neighbors.append(neighborSet)
firewares.append(fireware)
idx += 1
# 1.2.退出条件判断
if not neighbors:
break
# 1.3.找到邻居结点数最多的连通分量的maxIdx
maxIdx = 0
for i in range(1, len(neighbors)):
if len(neighbors[i]) > len(neighbors[maxIdx]):
maxIdx = i
# 1.4.将maxIdx对应的连通分量的节点全部设置为2，表示已经被防火墙隔离；将非maxIdx的连通分量的值标记为1，进行恢复，即将不等于-(maxIdx+1)且小于0的节点标记为1；并更新结果变量总防火墙数
for i in range(m):
for j in range(n):
if isInfected[i][j] == -(maxIdx + 1):
isInfected[i][j] = 2
elif isInfected[i][j] < 0:
isInfected[i][j] = 1
result += firewares[maxIdx]
# 1.5.将非maxIdx的连通分量的邻居结点标记为1，表示没被隔离的区域扩展一个单位
for i in range(len(neighbors)):
if i != maxIdx:
for r, c in neighbors[i]:
isInfected[r][c] = 1
return result4.执行结果
