題目描述
這是 LeetCode 上的 749. 隔離病毒 ,難度為 困難。
Tag : 「模拟」、「圖論搜尋」、「BFS」
病毒擴散得很快,現在你的任務是盡可能地通過安裝防火牆來隔離病毒。
假設世界由 的二維矩陣
isInfected
組成,
isInfected[i][j] == 0
表示該區域未感染病毒,而
isInfected[i][j] == 1
表示該區域已感染病毒。可以在任意
每天晚上,病毒會從被感染區域向相鄰未感染區域擴散,除非被防火牆隔離。現由于資源有限,每天你隻能安裝一系列防火牆來隔離其中一個被病毒感染的區域(一個區域或連續的一片區域),且該感染區域對未感染區域的威脅最大且 保證唯一 。
你需要努力使得最後有部分區域不被病毒感染,如果可以成功,那麼傳回需要使用的防火牆個數; 如果無法實作,則傳回在世界被病毒全部感染時已安裝的防火牆個數。
示例 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
提示:
-
is eitherisInfected[i][j]
or0
1
- 在整個描述的過程中,總有一個相鄰的病毒區域,它将在下一輪 嚴格地感染更多未受污染的方塊
搜尋模拟
根據題意,我們可以按天進行模拟,設計函數
getCnt
用于傳回當天會被安裝的防火牆數量,在
getCnt
内部我們會進行如下操作:
- 找出當天「對未感染區域的威脅最大」的區域,并将該區域進行隔離(将設定為);
- 對其他區域,進行步長為
考慮如何實作
getCnt
:我們需要以「連通塊」為機關進行處理,是以每次的
getCnt
操作,我們先重建一個與矩陣等大的判重數組
vis
,對于每個 且未被 标記為
True
的位置進行搜尋,搜尋過程使用
BFS
實作。
在
BFS
過程中,我們除了統計該連通塊所需要的防火牆數量 以外,還需要額外記錄目前連通塊中 的點集
s1
(簡稱為原集,含義為連通塊的格子集合),以及目前連通塊相鄰的 的點集
s2
(簡稱為擴充集,含義為将要被感染的格子集合)。
根據題意,在單次的
getCnt
中,我們需要在所有連通塊中取出其
s2
大小最大(對未感染區域的威脅最大)的連通塊進行隔離操作,而其餘連通塊則進行擴充操作。
是以我們可以使用兩個變量
max
和
ans
分别記錄所有
s2
中的最大值,以及取得最大
s2
所對應連通塊所需要的防火牆數量,同時需要使用兩個數組
l1
和
l2
分别記錄每個連通塊對應的「原集」和「擴充集」,友善我們後續進行「隔離」和「感染」。
Java 代碼:
class Solution {
int[][] g;
int n, m, ans;
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
boolean[][] vis;
int search(int _x, int {
int ans = 0;
Deque<int[]> d = new ArrayDeque<>();
vis[_x][_y] = true;
d.addLast(new int[]{_x, _y});
s1.add(_x * m + _y);
while (!d.isEmpty()) {
int[] info = d.pollFirst();
int x = info[0], y = info[1];
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1], loc = nx * m + ny;
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue;
if (g[nx][ny] == 1) {
s1.add(loc);
vis[nx][ny] = true;
d.addLast(new int[]{nx, ny});
} else if (g[nx][ny] == 0) {
s2.add(loc);
ans++;
}
}
}
return ans;
}
int getCnt() {
vis = new boolean[n][m];
int max = 0, ans = 0;
// l1: 每個連通塊的點集 s2: 每個連通塊的候選感染點集
List<Set<Integer>> l1 = new ArrayList<>(), l2 = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == 1 && !vis[i][j]) {
// s1: 目前連通塊的點集 s2: 目前連通塊的候選感染點集
Set<Integer> s1 = new HashSet<>(), s2 = new HashSet<>();
int b = search(i, j, s1, s2), a = s2.size();
if (a > max) {
max = a; ans = b;
}
l1.add(s1); l2.add(s2);
}
}
}
for (int i = 0; i < l2.size(); i++) {
for (int loc : l2.get(i).size() == max ? l1.get(i) : l2.get(i)) {
int x = loc / m, y = loc % m;
g[x][y] = l2.get(i).size() == max ? -1 : 1;
}
}
return ans;
}
public int containVirus(int[][] _g) {
g = _g;
n = g.length; m = g[0].length;
while (true) {
int cnt = getCnt();
if (cnt == 0) break;
ans += cnt;
}
return
TypeScript 代碼:
let g: number[][] = null
let n: number = 0, m: number = 0
let vis: boolean[][] = null
const dirs: number[][] = [[1,0],[-1,0],[0,1],[0,-1]]
function dfs(_x: number, _y: number, s1: Set<number>, s2: Set<number>): number {
let he = 0, ta = 0, ans = 0
let d: Array<number> = new Array<number>()
s1.add(_x * m + _y)
vis[_x][_y] = true
d[ta++] = _x * m + _y
while (he < ta) {
const poll = d[he++]
const x = Math.floor(poll / m), y = poll % m
for (const di of dirs) {
const nx = x + di[0], ny = y + di[1], loc = nx * m + ny
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue
if (g[nx][ny] == 1) {
s1.add(loc)
vis[nx][ny] = true
d[ta++] = loc
} else if (g[nx][ny] == 0) {
s2.add(loc)
ans++
}
}
}
return ans
}
function getCnt(): number {
vis = new Array<Array<boolean>>(n)
for (let i = 0; i < n; i++) vis[i] = new Array<boolean>(m).fill(false)
let max = 0, ans = 0
let l1: Array<Set<number>> = new Array<Set<number>>(), l2: Array<Set<number>> = new Array<Set<number>>()
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (g[i][j] == 1 && !vis[i][j]) {
let s1 = new Set<number>(), s2 = new Set<number>()
const b = dfs(i, j, s1, s2), a = s2.size
if (a > max) {
max = a; ans = b
}
l1.push(s1); l2.push(s2)
}
}
}
for (let i = 0; i < l2.length; i++) {
for (let loc of l2[i].size == max ? l1[i] : l2[i]) {
const x = Math.floor(loc / m), y = loc % m
g[x][y] = l2[i].size == max ? -1 : 1
}
}
return ans
}
function containVirus(_g: number[][]): number {
g = _g
n = g.length; m = g[0].length
let ans: number = 0
while (true) {
const cnt = getCnt()
if (cnt == 0) break
ans += cnt
}
return
- 時間複雜度:最多有天需要模拟,每天模拟複雜度,整體複雜度為
- 空間複雜度:
最後
這是我們「刷穿 LeetCode」系列文章的第
No.749
篇,系列開始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面,除了講解解題思路以外,還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。