Java实现 LeetCode 749 隔离病毒（DFS嵌套）
35 浏览量
2020-12-21
11:32:59
上传
评论
收藏 46KB PDF 举报
Java实现实现 LeetCode 749 隔离病毒（隔离病毒（DFS嵌套）嵌套）
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 个防火墙了。
说明:
grid 的行数和列数范围是 [1, 50]。
grid[i][j] 只包含 0 或 1 。
题目保证每次选取感染区域进行隔离时，一定存在唯一一个对未感染区域的威胁最大的区域。
class Solution {
int n, m;
boolean[][] visited;
Set set = new TreeSet();
public int containVirus(int[][] grid) {
int res = 0;
n = grid.length;
m = grid[0].length;
while (true){
visited = new boolean[n][m];
PriorityQueue q = new PriorityQueue(((o1, o2) -> o2[0]-o1[0]));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
评论0
最新资源