病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。

假设世界由二维矩阵组成，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 个防火墙了。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/contain-virus
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

这种题目娱乐玩玩可以，面试真要你手写，还是直接说拜拜吧。
出思路几分钟，写代码加调试几小时。。。

直接上代码

public class IsolateVirus {public static void main(String[] args) {int[][] grid =
//                {
//                {1,0,0,1,1,1,1,1,1,1},
//                {1,0,0,0,0,0,0,0,0,0},
//                {1,0,0,1,1,1,1,1,1,1},
//        };{{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}};System.out.println(new IsolateVirus().containVirus(grid));}List<Integer> spreadList = new ArrayList<>();List<Set<Integer>> areasList = new ArrayList<>();List<Set<Integer>> poteintialList = new ArrayList<>();List<Integer> controlList = new ArrayList<>();int[][] gridspre;int row,col;int[] wr = {-1,1,0,0};int[] hc = {0,0,-1,1};int wall=0;public int containVirus(int[][] grid) {row = grid.length;col=grid[0].length;gridspre = new int[row][col];for (int i=0;i<grid.length;i++) {for (int j = 0; j < grid[i].length; j++) {gridspre[i][j] = grid[i][j];}}for (int i=0;i<grid.length;i++){for (int j=0;j<grid[i].length;j++) {int a = grid[i][j];if (a==0){continue;}else {addAreasList(i, j);}}}int maxPot=0;int potSize = 0;if (poteintialList.size() ==0) {return wall;}for (int i=0;i<poteintialList.size();i++) {int tmpSize = poteintialList.get(i).size();if (tmpSize > potSize ){maxPot = i;potSize = tmpSize;}}Set<Integer> needWall =  areasList.get(maxPot);for (int w:needWall) {controlList.add(w);int i = w/col;int j = w%col;for (int d=0;d<4;d++) {int rd = i + wr[d];int cd = j + hc[d];if (rd<0||rd>row-1 || cd <0||cd>col-1) {continue;}if (grid[rd][cd] == 0) {wall ++;}}}spreadList.clear();areasList.clear();poteintialList.clear();for (int i=0;i<grid.length;i++){for (int j=0;j<grid[i].length;j++) {int a = grid[i][j];if (a==1){continue;}else {for (int d=0;d<4;d++) {int rd = i + wr[d];int cd = j + hc[d];if (rd<0||rd>row-1 || cd <0||cd>col-1) {continue;}int tmp =  rd * col + cd;if (grid[rd][cd] == 1 && !controlList.contains(tmp)) {gridspre[i][j] = 1;continue;}}}}}containVirus(gridspre);return wall;}private void addAreasList(int i, int j) {int tmp = i * col + j;if (!spreadList.contains(tmp) && !controlList.contains(tmp)) {Set<Integer> area = new HashSet<>();Set<Integer> potential = new HashSet<>();area.add(tmp);getLinkVirus(i,j,area, potential);poteintialList.add(potential);areasList.add(area);for (Integer a :area) {spreadList.add(a);}}}private void getLinkVirus(int i, int j, Set<Integer> area, Set<Integer> potential ) {for (int d=0;d<4;d++) {int rd = i + wr[d];int cd = j + hc[d];if (rd<0||rd>row-1 || cd <0||cd>col-1) {continue;}int tmp =  rd * col + cd;if (controlList.contains(tmp)) {continue;}if (gridspre[rd][cd] == 0) {potential.add(tmp);continue;}if (area.contains(tmp)) {continue;}area.add(tmp);getLinkVirus(rd,cd,area, potential);}}}