-
LeetCode刷题笔记-749. 隔离病毒-模拟+搜索
LeetCode刷题笔记-749. 隔离病毒-模拟+搜索
题目描述
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 个墙来隔离病毒区域。此时病毒已经被完全控制住了。- 1
- 2
- 3
- 4
- 5
示例 2：
输入: isInfected = [[1,1,1],[1,0,1],[1,1,1]] 输出: 4 解释: 虽然只保存了一个小区域，但却有四面墙。 注意，防火墙只建立在两个不同区域的共享边界上。- 1
- 2
- 3
- 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 个防火墙。- 1
- 2
- 3
解题思路
- 获取最大的感染面积区域和所需的防火墙数目
- 对最大感染面积区域的病毒进行阻断消杀
- 存活的病毒进行扩散处理
- 重复上述步骤，直到所需防火墙为0为止
如何获取最大感染面积
- 先遍历到病毒区域
- 对对每个病毒区域进行搜索
- 统计该区域可以感染的面积
- 统计该区域所需的防火墙
- 对当天最大病毒感染面积区域的病毒进行阻断消杀
- 对剩余病毒区域进行扩散处理
其中状态数
s需要特别注意，因为每一天一个位置可以有四个方向来感染，同时也可以有多个病毒区域来感染。因此要进行区分，这里就是通过状态数s来完成的。
func getMaxAreaNeedWalls() int { /* m: 最大的感染面积 cnt: 当前最大感染面积的区域所需的防火墙数目 x,y: 病毒区域 s: 表示当前区域要修建墙的状态,并且每个区域的s都是不一样的，互相不能影响 DFS完给s-1 */ m, cnt, x, y, s := 0, 0, -1, -1, -3 vis := make([][]int, r) // 访问标记数组 for i := 0; i < r; i++ { vis[i] = make([]int, c) } for i := 0; i < r; i++ { for j := 0; j < c; j++ { // 找到没有访问的病毒区域 if grid[i][j] == 1 && vis[i][j] != 1 { //当前区域需要的防火墙数量 cur = 0 //当前区域能感染的面积 temp := DFS(i, j, s, vis) if temp > m { m = temp cnt = cur x, y = i, j } s-- // 区域状态数递减 } } } // 没有病毒区域了只需0个防火墙 if x == -1 { return 0 } // 对当天最大病毒感染面积区域的病毒进行阻断消杀 toDead(x, y) // 重置访问数组 vis = make([][]int, r) for i := 0; i < r; i++ { vis[i] = make([]int, c) } for i := 0; i < r; i++ { for j := 0; j < c; j++ { // 对剩余病毒区域进行扩散处理 if grid[i][j] == 1 && vis[i][j] != 1 { spread(i, j, vis) } } } // 返回最大感染面积区域所需的防火墙数目 return cnt }- 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
如何进行阻断消杀
- 对该病毒区域的病毒进行死亡标记
grid[x][y] = -2 - 对病毒位置进行四个方向的DFS搜索，同时需要做访问标记。
func toDead(x, y int) { // 病毒消杀标记 grid[x][y] = -2 // 四处搜索 for i := 0; i < 4; i++ { x_, y_ := x+dir[i][0], y+dir[i][1] // 未越界且未访问且为病毒(状态转移) if x_ >= 0 && x_ < r && y_ >= 0 && y_ < c && grid[x_][y_] == 1 { toDead(x_, y_) } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
如何进行扩散处理
- 对当前病毒地点的四处进行DFS搜索。
- 如果为空，进行感染（边界条件）。
- 如果为病毒，继续搜索（状态转移）。
func spread(x, y int, vis [][]int) { // 访问标记 vis[x][y] = 1 // 四处搜索 for i := 0; i < 4; i++ { x_, y_ := x+dir[i][0], y+dir[i][1] // 未越界且未访问 if x_ >= 0 && x_ < r && y_ >= 0 && y_ < c && vis[x_][y_] != 1 { if grid[x_][y_] == 0 { // 边界条件 grid[x_][y_] = 1 vis[x_][y_] = 1 } else if grid[x_][y_] == 1 { // 状态转移 spread(x_, y_, vis) } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
如何对病毒区域搜索
- 对当前病毒地点的四处进行DFS搜索。
- 如果为空，防火墙数
cur（函数内的全局变量）自增，且未访问过的话感染面积自增（边界条件）。 - 如果为病毒，继续搜索（状态转移）。
func DFS(x, y, s int, vis [][]int) int { // 当前病毒区域所感染面积 res := 0 // 访问标记 vis[x][y] = 1 // 四处搜索 for i := 0; i < 4; i++ { x_, y_ := x+dir[i][0], y+dir[i][1] if x_ >= 0 && x_ < r && y_ >= 0 && y_ < c && vis[x_][y_] != 1 { // 未感染区域 if grid[x_][y_] == 0 { cur++ // 防火墙数目递增 // 判断是否为该病毒区域访问过 if vis[x_][y_] != s { res++ vis[x_][y_] = s } } else if grid[x_][y_] == 1 { // 感染区域(状态转移) res += DFS(x_, y_, s, vis) } } } return res }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
AC代码（Go语言）
// 方向数组 var dir [4][2]int = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} func containVirus(grid [][]int) int { /* 1. 获取最大的感染面积区域和所需的防火墙数目 2. 对最大感染面积区域的病毒进行阻断消杀 3. 存活的病毒进行扩散处理 4. 重复上述步骤，直到所需防火墙为0为止 */ res := 0 // 最终需要的防火墙数目 r, c := len(grid), len(grid[0]) // 当前区域的防火墙临时数目 cur := 0 // 对当前区域的防火墙内的病毒进行阻断消杀 var toDead func(int, int) // 对未隔离的病毒进行扩散 var spread func(int, int, [][]int) // 对当前区域的扩散范围进行搜索并统计所需防火墙 var DFS func(int, int, int, [][]int) int // 搜索一天内感染最大的区域所需要的防火墙数目 var getMaxAreaNeedWalls func() int getMaxAreaNeedWalls = func() int { /* m: 最大的感染面积 cnt: 当前最大感染面积的区域所需的防火墙数目 x,y: 病毒区域 s: 表示当前区域要修建墙的状态,并且每个区域的s都是不一样的，互相不能影响 DFS完给s-1 */ m, cnt, x, y, s := 0, 0, -1, -1, -3 vis := make([][]int, r) // 访问标记数组 for i := 0; i < r; i++ { vis[i] = make([]int, c) } for i := 0; i < r; i++ { for j := 0; j < c; j++ { // 找到没有访问的病毒区域 if grid[i][j] == 1 && vis[i][j] != 1 { //当前区域需要的防火墙数量 cur = 0 //当前区域能感染的面积 temp := DFS(i, j, s, vis) if temp > m { m = temp cnt = cur x, y = i, j } s-- // 区域状态数递减 } } } // 没有病毒区域了只需0个防火墙 if x == -1 { return 0 } // 对当天最大病毒感染面积区域的病毒进行阻断消杀 toDead(x, y) // 重置访问数组 vis = make([][]int, r) for i := 0; i < r; i++ { vis[i] = make([]int, c) } for i := 0; i < r; i++ { for j := 0; j < c; j++ { // 对剩余病毒区域进行扩散处理 if grid[i][j] == 1 && vis[i][j] != 1 { spread(i, j, vis) } } } // 返回最大感染面积区域所需的防火墙数目 return cnt } toDead = func(x, y int) { // 病毒消杀标记 grid[x][y] = -2 // 四处搜索 for i := 0; i < 4; i++ { x_, y_ := x+dir[i][0], y+dir[i][1] // 未越界且未访问且为病毒(状态转移) if x_ >= 0 && x_ < r && y_ >= 0 && y_ < c && grid[x_][y_] == 1 { toDead(x_, y_) } } } spread = func(x, y int, vis [][]int) { // 访问标记 vis[x][y] = 1 // 四处搜索 for i := 0; i < 4; i++ { x_, y_ := x+dir[i][0], y+dir[i][1] // 未越界且未访问 if x_ >= 0 && x_ < r && y_ >= 0 && y_ < c && vis[x_][y_] != 1 { if grid[x_][y_] == 0 { // 边界条件 grid[x_][y_] = 1 vis[x_][y_] = 1 } else if grid[x_][y_] == 1 { // 状态转移 spread(x_, y_, vis) } } } } DFS = func(x, y, s int, vis [][]int) int { // 当前病毒区域所感染面积 res := 0 // 访问标记 vis[x][y] = 1 // 四处搜索 for i := 0; i < 4; i++ { x_, y_ := x+dir[i][0], y+dir[i][1] if x_ >= 0 && x_ < r && y_ >= 0 && y_ < c && vis[x_][y_] != 1 { // 未感染区域 if grid[x_][y_] == 0 { cur++ // 防火墙数目递增 // 判断是否为该病毒区域访问过 if vis[x_][y_] != s { res++ vis[x_][y_] = s } } else if grid[x_][y_] == 1 { // 感染区域(状态转移) res += DFS(x_, y_, s, vis) } } } return res } for { // 每次大循环模拟一整天 walls := getMaxAreaNeedWalls() if walls == 0 { break } res += walls // 统计当天最大感染区域所需防火墙数目 } return res }- 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
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
-
相关阅读:
怎样避免执行走样
100天精通Andriod逆向——第2天：Android基础知识和jadx的使用
硬件科普系列之显示篇——LCD与OLED知多少
【每日一题】旋变字符串
使用ComposeDesktop开发一款桌面端多功能APK工具
Android之AMS原理分析
MySQL 中 WHERE 和 HAVING 的区别
广州穗雅医院健康汇：为什么口腔溃疡会反反复复？
Hadoop面试题
使用Spring框架创建一个RESTful API，实现学生信息的管理，包括资源的创建、读取、更新和删除。
- 原文地址：https://blog.csdn.net/qq_22328011/article/details/126151466
