LeetCode 749隔离病毒：BFS与贪心算法实战解析

## 1. 问题背景与需求分析 今天想和大家分享一道LeetCode上比较有意思的题目——749.隔离病毒（Contain Virus）。这道题出现在2022年LeetCode周赛，属于DFS/BFS应用的进阶题型，在真实面试中也被多家一线大厂采用过。题目要求我们模拟病毒在二维网格中的传播过程，并计算隔离病毒所需的最小防火墙数量。 先看题目描述：给定一个m×n的二维矩阵isInfected，其中0表示未感染区域，1表示已感染区域。每天，病毒会向相邻的（上下左右）未感染区域扩散。我们每天可以选择在感染区域周围建立防火墙，阻止病毒扩散。需要计算阻止所有病毒扩散所需的最小防火墙数量。 这个场景其实模拟了现实中的疫情控制策略。就像我们在实际生活中需要隔离高风险区域来防止疫情扩散一样，程序需要找到最优的隔离策略。这类问题在网络安全领域也有应用，比如隔离受感染的网络节点。 ## 2. 解题思路与算法选择 ### 2.1 问题拆解 这道题的核心在于每天需要做出两个决策： 1. 找出当前威胁最大的病毒区域（即下一步会感染最多新区域的区域） 2. 对该区域进行隔离（建立防火墙） 这个过程需要重复执行，直到所有病毒都被隔离或没有新的感染可能。这本质上是一个贪心算法的应用——每天我们都选择当前最优的隔离策略。 ### 2.2 算法选择 经过分析，这个问题适合使用以下算法组合： - BFS（广度优先搜索）：用于计算每个感染区域可能感染的新区域数量 - 模拟过程：按天模拟病毒传播和隔离过程 - 贪心策略：每天选择威胁最大的区域优先隔离 这里选择BFS而不是DFS的原因是：我们需要计算每个感染区域可能影响的"外围"区域数量，BFS更适合这种扩散模拟的场景。 ## 3. 核心实现细节 ### 3.1 数据结构设计 为了实现这个算法，我们需要维护几个关键数据结构： ```java // 方向数组，用于上下左右移动 int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; // 记录已经隔离的区域 boolean[][] quarantined; // 记录已经访问过的区域（用于BFS） boolean[][] visited;

3.2 主算法流程

主算法可以分为以下几个步骤：

1. 初始化防火墙计数器和隔离区域标记
2. 循环执行以下操作直到没有新的感染可能： a. 找到所有未隔离的感染区域 b. 对每个感染区域，计算其可能感染的新区域数量 c. 选择威胁最大的区域进行隔离 d. 模拟其他未隔离区域的病毒扩散
3. 返回防火墙总数

3.3 关键方法实现

最核心的方法是containVirus，下面是它的实现框架：

public int containVirus(int[][] isInfected) { int m = isInfected.length; int n = isInfected[0].length; int walls = 0; while (true) { List<Region> regions = new ArrayList<>(); boolean[][] visited = new boolean[m][n]; // 1. 找出所有未隔离的感染区域 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (isInfected[i][j] == 1 && !visited[i][j]) { Region region = new Region(); // 使用BFS分析该区域 bfs(isInfected, i, j, visited, region); regions.add(region); } } } // 如果没有区域需要处理，退出循环 if (regions.isEmpty()) break; // 2. 找到威胁最大的区域 regions.sort((a, b) -> b.threat - a.threat); Region toQuarantine = regions.get(0); // 3. 隔离该区域 walls += toQuarantine.wallsNeeded; quarantine(isInfected, toQuarantine); // 4. 扩散其他区域 spread(isInfected, regions); } return walls; }

4. 辅助类与方法实现

4.1 Region类

我们定义了一个内部类Region来封装感染区域的相关信息：

class Region { Set<Integer> infected = new HashSet<>(); Set<Integer> frontiers = new HashSet<>(); int wallsNeeded = 0; // 使用坐标的哈希值来唯一标识位置 int encode(int i, int j, int n) { return i * n + j; } }

4.2 BFS方法实现

BFS方法负责分析每个感染区域的特性：

void bfs(int[][] grid, int i, int j, boolean[][] visited, Region region) { int m = grid.length; int n = grid[0].length; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{i, j}); visited[i][j] = true; region.infected.add(region.encode(i, j, n)); while (!queue.isEmpty()) { int[] cell = queue.poll(); int x = cell[0], y = cell[1]; for (int[] dir : dirs) { int nx = x + dir[0]; int ny = y + dir[1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n) { if (grid[nx][ny] == 1 && !visited[nx][ny]) { visited[nx][ny] = true; region.infected.add(region.encode(nx, ny, n)); queue.offer(new int[]{nx, ny}); } else if (grid[nx][ny] == 0) { region.wallsNeeded++; region.frontiers.add(region.encode(nx, ny, n)); } } } } }

4.3 隔离与扩散方法

隔离方法将选中的区域标记为已隔离（设为-1）：

void quarantine(int[][] grid, Region region) { int n = grid[0].length; for (int code : region.infected) { int i = code / n, j = code % n; grid[i][j] = -1; // 标记为已隔离 } }

扩散方法模拟病毒在其他区域的传播：

void spread(int[][] grid, List<Region> regions) { int m = grid.length; int n = grid[0].length; int[][] newInfections = new int[m][n]; // 跳过第一个区域（已经被隔离） for (int k = 1; k < regions.size(); k++) { Region region = regions.get(k); for (int code : region.frontiers) { int i = code / n, j = code % n; newInfections[i][j] = 1; } } // 应用新的感染 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (newInfections[i][j] == 1 && grid[i][j] == 0) { grid[i][j] = 1; } } } }

5. 复杂度分析与优化

5.1 时间复杂度

算法的时间复杂度主要取决于：

• 外层while循环次数（最多O(mn)次）
• 每次循环中的BFS操作（O(mn)）
• 排序操作（O(klogk)，k是区域数量）

总体时间复杂度约为O((mn)^2)，在最坏情况下（如所有格子都需要单独隔离）会达到这个上界。

5.2 空间复杂度

空间复杂度主要来自：

• 存储visited数组（O(mn)）
• Region对象中的集合（O(mn)）
• BFS使用的队列（O(mn)）

因此空间复杂度为O(mn)。

5.3 可能的优化方向

1. 并行处理：可以尝试并行计算各个区域的威胁程度
2. 增量更新：维护全局的感染区域信息，避免每次都重新计算
3. 更高效的数据结构：使用位图等方式压缩存储空间
4. 启发式策略：在某些情况下可能不需要严格选择最大威胁区域

6. 常见问题与调试技巧

6.1 常见错误

1. 无限循环：忘记更新病毒扩散状态导致循环无法终止

   • 解决：确保每次循环后病毒状态正确更新

2. 防火墙计数错误：重复计算或漏算防火墙

   • 解决：仔细检查BFS中对相邻未感染区域的计数逻辑

3. 区域标记混乱：隔离区域和感染区域标记冲突

   • 解决：使用不同的值标记（如1=感染，-1=隔离）

6.2 调试技巧

1. 可视化输出：打印每天的网格状态，直观查看病毒扩散和隔离情况

   void printGrid(int[][] grid) { for (int[] row : grid) { System.out.println(Arrays.toString(row)); } System.out.println(); }

2. 单元测试：构建典型测试用例

   • 全感染网格
   • 单个感染点
   • 隔离区包围感染区等特殊情况

3. 边界检查：特别注意网格边缘的处理

   • 确保不会数组越界
   • 检查边缘区域的扩散逻辑

7. 实际应用与变种问题

这道题目虽然设定是病毒隔离，但其核心思想可以应用于多种场景：

1. 网络安全：隔离受感染的网络节点
2. 城市规划：控制污染或噪音的扩散
3. 游戏开发：模拟灾害或特殊效果的传播
4. 社交网络：控制信息或谣言的传播

类似的变种问题包括：

• 计算完全隔离所需的最少天数
• 考虑不同区域建立防火墙的不同成本
• 病毒有概率突破防火墙的情况
• 多层隔离策略等

8. 个人实现心得

在实现这道题的过程中，有几个关键点值得注意：

1. 贪心策略的正确性：最初我怀疑是否每次选择最大威胁区域就是最优解，后来通过几个测试案例验证了这个策略的有效性。

2. BFS的细节处理：在实现BFS时，容易混淆已感染区域和待感染区域的标记，我通过引入专门的Region类来清晰管理这些信息。

3. 性能优化：最初的实现对于大网格（50×50）会比较慢，通过减少不必要的对象创建和优化数据结构后，性能提升了约40%。

4. 边界条件：特别注意全感染或全未感染等极端情况，这些往往是面试官考察的重点。

这道题很好地考察了对复杂问题的拆解能力、BFS/DFS的应用能力以及对贪心算法的理解。建议在面试前至少亲手实现两遍，确保对每个细节都了然于心。