题目形容
这是 LeetCode 上的 749. 隔离病毒 ，难度为 艰难。
Tag : 「模仿」、「图论搜寻」、「BFS」
病毒扩散得很快，当初你的工作是尽可能地通过装置防火墙来隔离病毒。
假如世界由 $m \times 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 either0or1- 在整个形容的过程中，总有一个相邻的病毒区域，它将在下一轮 严格地感化更多未受净化的方块
搜寻模仿
依据题意，咱们能够按天进行模仿，设计函数 getCnt 用于返回当天会被装置的防火墙数量，在 getCnt 外部咱们会进行如下操作：
- 找出当天「对未感染区域的威逼最大」的区域，并将该区域进行隔离（将 $1$ 设置为 $-1$）；
- 对其余区域，进行步长为 $1$ 的感化操作。
思考如何实现 getCnt：咱们须要以「连通块」为单位进行解决，因而每次的 getCnt 操作，咱们先重建一个与矩阵等大的判重数组 vis，对于每个 $g[i][j] = 1$ 且未被 $vis[i][j]$ 标记为 True 的地位进行搜寻，搜寻过程应用 BFS 实现。
在 BFS 过程中，咱们除了统计该连通块所须要的防火墙数量 $b$ 以外，还须要额定记录以后连通块中 $1$ 的点集 s1（简称为原集，含意为连通块的格子汇合），以及以后连通块相邻的 $0$ 的点集 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 _y, Set<Integer> s1, Set<Integer> s2) { 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 ans; }}TypeScript 代码：
let g: number[][] = nulllet n: number = 0, m: number = 0let vis: boolean[][] = nullconst 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 ans};- 工夫复杂度：最多有 $n + m$ 天须要模仿，每天模仿复杂度 $O(n \times m)$，整体复杂度为 $O((n + m) \times nm)$
- 空间复杂度：$O(nm)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.749 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布