题目
题目描述
病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。
假设世界由二维矩阵组成，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 面防火墙，就有一小区域可以幸存，不被病毒感染。
注意不需要在世界边界建立防火墙。
题解
题目意思是对病毒区域建立防火墙进行隔离，但是在有两个条件
条件1：就是每天只能隔离一个病毒区域，并且每天没被隔离的病毒都会扩散一层，
条件2：每次选择隔离感染区域需对未感染区域的威胁最大且保证唯一
所以我们要做的
第一步就是寻找最大威胁感染区域并且统计需要的防火墙的个数
第二步把找到最大威胁感染区域在地图上清除
第三步没被隔离的病毒扩散一层
然后循环这些步骤知道找不到最大威胁感染区域
所以在第一步的时候我们遍历地图找到一个感染点然后对其标记并且通过深搜找到其所在的感染区域，在深搜的时候我们肯定会遇到未感染的点而遇到次数就是我们要建立的防火墙个数，但是我们要比较的是未感染的大小（因此我们每次搜索到未感染的点都要判断是否走过），所以我们要同时统计这两个数量 然后在搜索完成后返回。但是我们在一次遍历中可能会多次遇到同一个未感染的点所以在搜索中我们要对每个未感染的点进行涂色（不同的病毒区域可能会对一个点进行多次感染）当我们找到最大感染点的时候后面的步骤就简单了
ps: 要注意找到有相同的个数可感染范围的最大威胁感染区域时 要对他进行一个筛选并且选择使用防火墙个数多的那个
pss：当前提交代码可再优化 进行一些剪枝时间可以更加快 然而回家懒得改了。。。。。
代码
class lc749 {
int[][] map;
int[][] visit;
int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public int containVirus(int[][] grid) {
map = grid;
int sum = 0;
int[] max;
if (grid.length == 0)
return 0;
int row = grid.length;
int col = grid[0].length;
int count = 1;
int[] dit = new int[2];
visit = new int[grid.length][grid[0].length];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(" " + map[i][j]);
}
System.out.println("");
}
System.out.println("");
while (true) {
max = new int[]{0, 0};
int flag = 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (visit[i][j] == 0 && map[i][j] >= 1) {
visit[i][j] = 1;
int[] num = dfs(i, j, new int[]{0, 0}, flag);
if (num[0] > max[0]) {
max = num;
dit[0] = i;
dit[1] = j;
} else if (num[0] == max[0] && num[1] > max[1]) {
max = num;
dit[0] = i;
dit[1] = j;
}
flag++;
}
}
}
if (max[0] == 0)
break;
map[dit[0]][dit[1]] = -1;
clear1(dit[0], dit[1]);
getNext(row, col, count);
visit = new int[grid.length][grid[0].length];
sum += max[1];
count++;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print(" " + map[i][j]);
}
System.out.println("");
}
System.out.println("");
}
return sum;
}
private void getNext(int row, int col, int count) {
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (map[i][j] == 0) {
for (int k = 0; k < 4; k++) {
if (i + dir[k][0] >= 0 && i + dir[k][0] < map.length && j + dir[k][1] >= 0 && j + dir[k][1] < map[0].length)
if (map[i + dir[k][0]][j + dir[k][1]] <= count && map[i + dir[k][0]][j + dir[k][1]] > 0) {
map[i][j] = count + 1;
break;
}
}
}
}
}
}
public void clear1(int row, int col) {
for (int i = 0; i < 4; i++) {
if (row + dir[i][0] >= 0 && row + dir[i][0] < map.length && col + dir[i][1] >= 0 && col + dir[i][1] < map[0].length)
if (map[row + dir[i][0]][col + dir[i][1]] > 0) {
map[row + dir[i][0]][col + dir[i][1]] = -1;
clear1(row + dir[i][0], col + dir[i][1]);
}
}
}
public int[] dfs(int row, int col, int[] sum, int flag) {
for (int i = 0; i < 4; i++) {
if (row + dir[i][0] >= 0 && row + dir[i][0] < map.length && col + dir[i][1] >= 0 && col + dir[i][1] < map[0].length)
if (map[row + dir[i][0]][col + dir[i][1]] == 0) {
if (visit[row + dir[i][0]][col + dir[i][1]] != flag)
sum[0]++;
visit[row + dir[i][0]][col + dir[i][1]] = flag;
sum[1]++;
} else if (map[row + dir[i][0]][col + dir[i][1]] == -1) {
} else {
if (visit[row + dir[i][0]][col + dir[i][1]] == 1)
continue;
visit[row + dir[i][0]][col + dir[i][1]] = 1;
sum = dfs(row + dir[i][0], col + dir[i][1], sum, flag);
}
}
return sum;
}
}
提交截图
image.png
网友评论