[数据结构与算法]749 隔离病毒（递归、模拟）

1. 问题描述：

病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。假设世界由二维矩阵组成，0 表示该区域未感染病毒，而 1 表示该区域已感染病毒。可以在任意 2 个四方向相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且保证唯一。你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。

示例 1：

输入: 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]]
输出: 10

说明:

一共有两块被病毒感染的区域: 从左往右第一块需要 5 个防火墙，同时若该区域不隔离，晚上将感染 5 个未感染区域（即被威胁的未感染区域个数为 5）;
第二块需要 4 个防火墙，同理被威胁的未感染区域个数是 4。因此，第一天先隔离左边的感染区域，经过一晚后，病毒传播后世界如下:
[[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]]
第二题，只剩下一块未隔离的被感染的连续区域，此时需要安装 5 个防火墙，且安装完毕后病毒隔离任务完成。

示例 2：

输入: grid =?
[[1,1,1],
?[1,0,1],
?[1,1,1]]
输出: 4

说明:?

此时只需要安装 4 面防火墙，就有一小区域可以幸存，不被病毒感染。
注意不需要在世界边界建立防火墙。

示例?3:

输入: 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]]
输出: 13

说明:?

在隔离右边感染区域后，隔离左边病毒区域只需要 2 个防火墙了。

说明:

grid 的行数和列数范围是 [1, 50]。
?grid[i][j]?只包含?0?或?1?。
题目保证每次选取感染区域进行隔离时，一定存在唯一一个对未感染区域的威胁最大的区域。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contain-virus
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 思路分析：

分析题目可以知道我们根据题目的描述模拟整个过程即可，首先我们需要找到当前所有为1的联通块，计算出所有联通块中周围为0的最大数目，0的数目表示当前联通块中下一次被病毒感染的数量，找联通块可以使用dfs，并且我们在dfs搜索的过程中记录下每个联通块中需要安装的防火墙的数目（在dfs搜索的过程每搜索一个1的位置若上下左右四个方向是0那么计数加1），并且记录下每个联通块中周围为0的坐标位置（因为每一次只能在一个联通块中安装防火墙所以其余没有安装防火墙的病毒的区域下一次就会被感染需要将这些位置置为1），通过对当前整个矩阵进行dfs搜索之后那么我们就可以找到下一次病毒感染数量最多的那个联通块和需要安装的最多的防火墙的数量，在dfs的过程中记录下了所有联通块1的周围0的坐标，这样我们可以将没有安装过的墙的联通块周围1中相邻的0的位置全置为1表示下一次这些位置就被感染了，并且将安装防火墙的那个联通块中的所有1置为-1表示已访问过这些位置了，整个过程需要注意一些细节问题即可。（其中涉及到的细节比较多）

3. 代码如下：

from typing import List


class Solution:
    # 表示右左下上四个方向
    pos = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    def containVirus(self, g: List[List[int]]) -> int:
        res = 0
        while True:
            count = self.find(g)
            if count == 0: break
            res += count
        return res
    
    # 寻找当前所有连通块中下一次被病毒感染数量最多的联通块, 返回当前需要的最多防火墙的数目
    def find(self, g: List[List[int]]):
        n, m = len(g), len(g[0])
        # 每一次都需要初始化sta表示新的状态
        sta = [[0] * len(g[0]) for i in range(len(g))]
        ss = list()
        # path记录当前需要最多防火墙的联通块中所有1的位置
        path = list()
        # res记录当前需要的最多防火墙的数目
        res = 0
        # count记录当前联通块中下一次被感染的最多数量
        count = 0
        for i in range(n):
            for j in range(m):
                if g[i][j] == 1 and sta[i][j] == 0:
                    # 每一次的时候需要新建_path
                    _path = list()
                    # S记录当前联通块1中周围为0的坐标, S为set类型这样可以避免重复加入某些坐标
                    S = set()
                    # t为需要的防火墙数量
                    t = self.dfs(g, S, sta, _path, i, j)
                    # 联通块中周围的0的数目更多那么更新count/res/path
                    if len(S) > count:
                        res = t
                        # 更新全局需要安装最多防火墙数量对应的位置
                        path = _path
                        count = len(S)
                    # 添加联通块中周围0的坐标方便后面将其置为1(将将坐标加入到set中这样可以避免重复), 因为每一次只能够处理一个联通块中周围的防火墙, 所以下一次的时候没有安装防火墙的靠近病毒的位置就被感染了
                    ss.append(S)
        # 将安装防火墙位置中联通块1的位置置为-1
        for x in path:
            g[x[0]][x[1]] = -1
        # 将下一次被感染的位置全部标记为1
        for x in ss:
            if len(x) != count:
                for _x, _y in x:
                    g[_x][_y] = 1
        return res

    def dfs(self, g: List[List[int]], S: set, sta: List[List[int]], _path: List[tuple], x: int, y: int):
        # 标记当前位置已经被访问
        sta[x][y] = 1
        # 记录当前联通块1访问过的位置
        _path.append((x, y))
        res = 0
        for i in range(4):
            x0, y0 = x + self.pos[i][0], y + self.pos[i][1]
            if 0 <= x0 < len(g) and 0 <= y0 < len(g[0]):
                if g[x0][y0] == 0:
                    # 添加联通块周围0的位置
                    S.add((x0, y0))
                    res += 1
                elif g[x0][y0] == 1 and sta[x0][y0] == 0:
                    res += self.dfs(g, S, sta, _path, x0, y0)
        return res