算法题“隔离病毒”的解题思路：基于BFS/DFS的模拟与连通块分析

“国企稳定”这四个字，真到工资条上，有时候稳定得让人沉默了。最近有网友晒出弟弟在国企的工资单，实发金额不到两千，引发了广泛讨论。很多时候，人们羡慕的可能不是那份工资，而是那个“听起来不错”的单位名头。

评论区的声音也很真实。有人认为，国企岗位也要分地区、看具体岗位和补贴，否则可能真的只是顶着一个“好单位”的名号，过着每月精打细算的日子。说到底，工作名头是给别人看的，到账的金额才是给自己过的。

算法题：隔离病毒

聊完现实，咱们换个脑子，来看一道有趣的算法题：“隔离病毒”。这道题本质上是一个模拟 + 连通块搜索的过程。每一轮你需要完成四件事：

1. 找出当前所有的病毒连通块。
2. 计算每个连通块下一轮能感染哪些空白格子。
3. 选出威胁最大（即能感染空白格最多）的那一块，将其彻底隔离（修墙）。
4. 剩下的病毒块则向外扩散一轮。

解题时容易出错的地方主要有两个：一是“威胁最大”的比较依据是该病毒块能感染的空白格数量，而不是病毒格子本身的数量；二是需要修建的墙的数量，计算的是病毒格与相邻空白格之间的接触边的数量，而非空白格的数量。

代码实现上，我习惯先写一个辅助函数，用来探索并收集一个病毒区域的信息：

def explore(grid, i, j, vis):
    m, n = len(grid), len(grid[0])
    stack = [(i, j)]
    vis.add((i, j))
    cells = []
    frontier = set()
    walls = 0

    while stack:
        x, y = stack.pop()
        cells.append((x, y))
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < m and 0 <= ny < n):
                continue
            if grid[nx][ny] == 1 and (nx, ny) not in vis:
                vis.add((nx, ny))
                stack.append((nx, ny))
            elif grid[nx][ny] == 0:
                frontier.add((nx, ny))
                walls += 1
    return cells, frontier, walls

这里的 frontier 记录了这片区域下一轮能感染到的所有空白格（使用集合去重），而 walls 则是需要为这个区域修建的墙的总数。注意，一个空白格可能被同一病毒区域从多个方向接触，所以 frontier 需要去重，但 walls 必须累加每次接触，这个地方很容易算错。

主体的模拟流程并不复杂，按轮次进行即可：

class Solution:
    def containVirus(self, isInfected):
        m, n = len(isInfected), len(isInfected[0])
        ans = 0

        while True:
            vis = set()
            regions = []

            for i in range(m):
                for j in range(n):
                    if isInfected[i][j] == 1 and (i, j) not in vis:
                        regions.append(explore(isInfected, i, j, vis))

            if not regions:
                break

            idx = max(range(len(regions)), key=lambda k: len(regions[k][1]))
            if len(regions[idx][1]) == 0:
                break

            ans += regions[idx][2]

            for k, (cells, frontier, _) in enumerate(regions):
                if k == idx:
                    for x, y in cells:
                        isInfected[x][y] = -1
                else:
                    for x, y in frontier:
                        isInfected[x][y] = 1

        return ans

我更喜欢将被隔离的病毒格标记为 -1，这样在后续的扫描中就能明确知道这块区域已经被封锁，不会再参与扩散。如果继续用 1 表示，后续的逻辑会变得混乱。

这道题算法上并不高深，DFS或BFS也很基础，难点在于要在一轮中完整地收集所有区域的状态信息。你不能边扫描边扩散，也不能一发现某个区域威胁大就立刻隔离，否则会打乱同一轮次的数据。老老实实遵循“先统计，再决策，后更新”的步骤，代码才会清晰稳健。

无论是讨论薪资结构还是推敲算法细节，关键在于厘清核心逻辑与常见陷阱。希望这篇结合了生活观察与算法解析的文章能给你带来一些启发。欢迎在云栈社区分享你的解题思路或职场见解。