leetcode 749. 隔离病毒

题目描述

病毒扩散得很快,现在你的任务是尽可能地通过安装防火墙来隔离病毒。
假设世界由二维矩阵组成,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 个防火墙了。

说明:

  1. grid 的行数和列数范围是 [1, 50]。
  2. grid[i][j] 只包含 0 或 1 。
  3. 题目保证每次选取感染区域进行隔离时,一定存在唯一一个对未感染区域的威胁最大的区域。

题解

找出每一处病毒区域和所需防火墙数的对应virusMap,以及每一处病毒区域威胁到的未感染的区块数目uninfectedCells,并找出最具威胁的病毒区域maxVirus;然后maxVirus对应的病毒区域变为2表示已隔离,其他病毒区域则感染周边区块变为1;继续下次循环直到virusMap[maxVirus] == 0

示例代码(go)

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
func containVirus(grid [][]int) int {
firewalls := 0
if len(grid) == 0 {
return firewalls
}

for {
virusMap, maxVirus := getVirusMap(grid)
if virusMap[maxVirus] == 0 {
break
}
cellsTo2(grid, virusMap, maxVirus)
cellsTo1(grid, virusMap, maxVirus)
firewalls += virusMap[maxVirus]
}
return firewalls
}

func getVirusMap(grid [][]int) (map[int]int, int) {
col := len(grid)
row := len(grid[0])
direction := [][]int{[]int{0, -1}, []int{-1, 0}, []int{0, 1}, []int{1, 0}}
maxUninfectedCells := 0
maxVirus := 0
virusMap := make(map[int]int)
infectedCellsVisted := make(map[int]bool)
for i := 0; i < col; i++ {
for j := 0; j < row; j++ {
if grid[i][j] == 1 && !infectedCellsVisted[i*row+j] {
virusList := []int{i*row+j}
infectedCellsVisted[i*row+j] = true
uninfectedCellsVisted := make(map[int]bool)
needWalls := 0
uninfectedCells := 0
for len(virusList) > 0 {
virus := virusList[0]
virusList = virusList[1:]
for _, v := range direction {
ii := virus / row + v[0]
jj := virus % row + v[1]
if ii >= 0 && ii < col && jj >= 0 && jj < row {
if grid[ii][jj] == 0 {
needWalls++
}
if grid[ii][jj] == 0 && !uninfectedCellsVisted[ii*row+jj] {
uninfectedCellsVisted[ii*row+jj] = true
uninfectedCells++
}
if grid[ii][jj] == 1 && !infectedCellsVisted[ii*row+jj] {
infectedCellsVisted[ii*row+jj] = true
virusList = append(virusList, ii*row+jj)
}
}
}
}
virusMap[i*row+j] = needWalls
if uninfectedCells > maxUninfectedCells {
maxUninfectedCells = uninfectedCells
maxVirus = i * row +j
}
}
}
}
return virusMap, maxVirus
}

func cellsTo2(grid [][]int, virusMap map[int]int, maxVirus int) {
col := len(grid)
row := len(grid[0])
direction := [][]int{[]int{0, -1}, []int{-1, 0}, []int{0, 1}, []int{1, 0}}
virusList := []int{maxVirus}
grid[maxVirus / row][maxVirus % row] = 2
for len(virusList) > 0 {
virus := virusList[0]
virusList = virusList[1:]
for _, v := range direction {
ii := virus / row + v[0]
jj := virus % row + v[1]
if ii >= 0 && ii < col && jj >= 0 && jj < row {
if grid[ii][jj] == 1 {
grid[ii][jj] = 2
virusList = append(virusList, ii*row+jj)
}
}
}
}
}

func cellsTo1(grid [][]int, virusMap map[int]int, maxVirus int) {
visted := make(map[int]bool)
col := len(grid)
row := len(grid[0])
direction := [][]int{[]int{0, -1}, []int{-1, 0}, []int{0, 1}, []int{1, 0}}
for k,_ := range virusMap {
if k != maxVirus {
virusList := []int{k}
visted[k] = true
for len(virusList) > 0 {
virus := virusList[0]
virusList = virusList[1:]
for _, v := range direction {
ii := virus / row + v[0]
jj := virus % row + v[1]
if ii >= 0 && ii < col && jj >= 0 && jj < row {
if grid[ii][jj] == 0 {
grid[ii][jj] = 1
visted[ii*row+jj] = true
}
if grid[ii][jj] == 1 && !visted[ii*row+jj] {
visted[ii*row+jj] = true
virusList = append(virusList, ii*row+jj)
}
}
}
}
}
}
}