题目描述
病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
假设世界由 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.lengthn == isInfected[i].length1 <= m, n <= 50isInfected[i][j] is either 0 or 1- 在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮 严格地感染更多未受污染的方块
解法
方法一：DFS 暴力模拟
DFS 找到每个病毒区域 areas[i]，同时记录每个区域边界节点 boundaries[i] 以及周长 c[i]。
接着对威胁最大的病毒区域进行隔离，累加所需的防火墙数量。
剩余的病毒区域向外感染一个区域。
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
43 | class Solution:
def containVirus(self, isInfected: List[List[int]]) -> int:
def dfs(i, j):
vis[i][j] = True
areas[-1].append((i, j))
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if isInfected[x][y] == 1 and not vis[x][y]:
dfs(x, y)
elif isInfected[x][y] == 0:
c[-1] += 1
boundaries[-1].add((x, y))
m, n = len(isInfected), len(isInfected[0])
ans = 0
while 1:
vis = [[False] * n for _ in range(m)]
areas = []
c = []
boundaries = []
for i, row in enumerate(isInfected):
for j, v in enumerate(row):
if v == 1 and not vis[i][j]:
areas.append([])
boundaries.append(set())
c.append(0)
dfs(i, j)
if not areas:
break
idx = boundaries.index(max(boundaries, key=len))
ans += c[idx]
for k, area in enumerate(areas):
if k == idx:
for i, j in area:
isInfected[i][j] = -1
else:
for i, j in area:
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:
isInfected[x][y] = 1
return ans
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 | class Solution {
private static final int[] DIRS = {-1, 0, 1, 0, -1};
private List<Integer> c = new ArrayList<>();
private List<List<Integer>> areas = new ArrayList<>();
private List<Set<Integer>> boundaries = new ArrayList<>();
private int[][] infected;
private boolean[][] vis;
private int m;
private int n;
public int containVirus(int[][] isInfected) {
infected = isInfected;
m = infected.length;
n = infected[0].length;
vis = new boolean[m][n];
int ans = 0;
while (true) {
for (boolean[] row : vis) {
Arrays.fill(row, false);
}
c.clear();
areas.clear();
boundaries.clear();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (infected[i][j] == 1 && !vis[i][j]) {
c.add(0);
areas.add(new ArrayList<>());
boundaries.add(new HashSet<>());
dfs(i, j);
}
}
}
if (areas.isEmpty()) {
break;
}
int idx = max(boundaries);
ans += c.get(idx);
for (int t = 0; t < areas.size(); ++t) {
if (t == idx) {
for (int v : areas.get(t)) {
int i = v / n, j = v % n;
infected[i][j] = -1;
}
} else {
for (int v : areas.get(t)) {
int i = v / n, j = v % n;
for (int k = 0; k < 4; ++k) {
int x = i + DIRS[k], y = j + DIRS[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && infected[x][y] == 0) {
infected[x][y] = 1;
}
}
}
}
}
}
return ans;
}
private int max(List<Set<Integer>> boundaries) {
int idx = 0;
int mx = boundaries.get(0).size();
for (int i = 1; i < boundaries.size(); ++i) {
int t = boundaries.get(i).size();
if (mx < t) {
mx = t;
idx = i;
}
}
return idx;
}
private void dfs(int i, int j) {
vis[i][j] = true;
int idx = areas.size() - 1;
areas.get(idx).add(i * n + j);
for (int k = 0; k < 4; ++k) {
int x = i + DIRS[k], y = j + DIRS[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (infected[x][y] == 1 && !vis[x][y]) {
dfs(x, y);
} else if (infected[x][y] == 0) {
c.set(idx, c.get(idx) + 1);
boundaries.get(idx).add(x * n + y);
}
}
}
}
}
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85 | class Solution {
public:
const vector<int> dirs = {-1, 0, 1, 0, -1};
vector<int> c;
vector<vector<int>> areas;
vector<unordered_set<int>> boundaries;
vector<vector<int>> infected;
vector<vector<bool>> vis;
int m;
int n;
int containVirus(vector<vector<int>>& isInfected) {
infected = isInfected;
m = infected.size();
n = infected[0].size();
vis.assign(m, vector<bool>(n));
int ans = 0;
while (1) {
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) vis[i][j] = false;
c.clear();
areas.clear();
boundaries.clear();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (infected[i][j] == 1 && !vis[i][j]) {
c.push_back(0);
areas.push_back({});
boundaries.push_back({});
dfs(i, j);
}
}
}
if (areas.empty()) break;
int idx = getMax();
ans += c[idx];
for (int t = 0; t < areas.size(); ++t) {
if (t == idx) {
for (int v : areas[t]) {
int i = v / n, j = v % n;
infected[i][j] = -1;
}
} else {
for (int v : areas[t]) {
int i = v / n, j = v % n;
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && infected[x][y] == 0) infected[x][y] = 1;
}
}
}
}
}
return ans;
}
int getMax() {
int idx = 0;
int mx = boundaries[0].size();
for (int i = 1; i < boundaries.size(); ++i) {
int t = boundaries[i].size();
if (mx < t) {
mx = t;
idx = i;
}
}
return idx;
}
void dfs(int i, int j) {
vis[i][j] = true;
areas.back().push_back(i * n + j);
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k], y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (infected[x][y] == 1 && !vis[x][y])
dfs(x, y);
else if (infected[x][y] == 0) {
c.back() += 1;
boundaries.back().insert(x * n + y);
}
}
}
}
};
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 | func containVirus(isInfected [][]int) int {
m, n := len(isInfected), len(isInfected[0])
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
max := func(boundaries []map[int]bool) int {
idx := 0
mx := len(boundaries[0])
for i, v := range boundaries {
t := len(v)
if mx < t {
mx = t
idx = i
}
}
return idx
}
for {
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
areas := []map[int]bool{}
boundaries := []map[int]bool{}
c := []int{}
var dfs func(i, j int)
dfs = func(i, j int) {
vis[i][j] = true
idx := len(areas) - 1
areas[idx][i*n+j] = true
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n {
if isInfected[x][y] == 1 && !vis[x][y] {
dfs(x, y)
} else if isInfected[x][y] == 0 {
c[idx]++
boundaries[idx][x*n+y] = true
}
}
}
}
for i, row := range isInfected {
for j, v := range row {
if v == 1 && !vis[i][j] {
areas = append(areas, map[int]bool{})
boundaries = append(boundaries, map[int]bool{})
c = append(c, 0)
dfs(i, j)
}
}
}
if len(areas) == 0 {
break
}
idx := max(boundaries)
ans += c[idx]
for t, area := range areas {
if t == idx {
for v := range area {
i, j := v/n, v%n
isInfected[i][j] = -1
}
} else {
for v := range area {
i, j := v/n, v%n
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && isInfected[x][y] == 0 {
isInfected[x][y] = 1
}
}
}
}
}
}
return ans
}
|