0749：隔离病毒（2277 分）

2017-01-18 约 901 字预计阅读 2 分钟次阅读

力扣第 749 题

题目

病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。

假设世界由 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.length
n == isInfected[i].length
1 <= m, n <= 50
isInfected[i][j] is either 0 or 1
在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮 严格地感染更多未受污染的方块

相似问题：

2954：统计感冒序列的数目（2644 分）

分析

模拟即可
- 数据较小，可以每次遍历获取所有的病毒连通块
- 对于某个连通块，相邻的 0 的个数即是威胁度，与 0 相邻的边即是防火墙个数
- 隔离的连通块可以将值改为 -1，从而不影响后续操作
注意到重要的只是连通块的边界，因此维护边界集合，每轮只遍历边界即可
- 只通过边界更新连通块，需要用到并查集

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


class Solution:
    def containVirus(self, isInfected: List[List[int]]) -> int:
        def find(x):
            if f[x]!=x:
                f[x] = find(f[x])
            return f[x]

        def union(x,y):
            f[find(x)] = find(y)

        A = isInfected
        m, n = len(A), len(A[0])
        res = 0
        f = list(range(m*n))
        V = {(i,j) for i in range(m) for j in range(n) if A[i][j]==1}
        while True:
            for i,j in V:
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if (x,y) in V:
                        union(i*n+j,x*n+y)
            T = defaultdict(set)
            W = defaultdict(int)
            for i,j in V:
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0<=x<m and 0<=y<n and A[x][y]==0:
                        T[find((i*n+j))].add((x,y))
                        W[find((i*n+j))] += 1
            if not T:
                break
            mp = max(T,key=lambda p:len(T[p]))
            res += W[mp]
            for i,j in V:
                if find(i*n+j)==mp:
                    A[i][j] = -1
            del T[mp]
            V = set()
            for p in T:
                for x,y in T[p]:
                    A[x][y] = 1
                    union(p,x*n+y)
                    V.add((x,y))
        return res

50 ms

目录

0749：隔离病毒（2277 分）

题目

分析

解答