Java实现 LeetCode 749 隔离病毒（DFS嵌套）

灰太狼 2023-07-25 14:24 12阅读 0赞

## 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<Integer> 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<int[]> q = new PriorityQueue<>(((o1, o2) -> o2[0]-o1[0]));
                for (int i = 0; i < n; i++){ 
                    for (int j = 0; j < m; j++){ 
                        if (!visited[i][j] && grid[i][j] == 1){ 
                            set.clear();
                            int barriers = dfs(grid, i, j);
                            int infected = set.size();
                            q.offer(new int[]{ infected, barriers, index(i, j)});
                        }
                    }
                }
                if (q.size() == 0){ 
                    break;
                }
                int[] t = q.poll();
                res += t[1];
                dfs1(grid, t[2] / m, t[2] % m);
                for (int i = 0; i < n; i++){ 
                    Arrays.fill(visited[i], false);
                }
                for (int i = 0; i < n; i++){ 
                    for (int j = 0; j < m; j++){ 
                        if (!visited[i][j] && grid[i][j] == 1){ 
                            dfs2(grid, i, j);
                        }
                    }
                }
    
            }
            return res;
        }
    
        private void dfs2(int[][] grid, int i, int j) { 
            if (grid[i][j] == 2){ 
                return;
            }
            visited[i][j] = true;
            if (i - 1 >= 0 && !visited[i - 1][j]){ 
                if (grid[i - 1][j] == 0){ 
                    grid[i - 1][j] = 1;
                    visited[i - 1][j] = true;
                }else{ 
                    dfs2(grid, i - 1, j);
                }
            }
            if (i + 1 < n && !visited[i + 1][j]){ 
                if (grid[i + 1][j] == 0){ 
                    grid[i + 1][j] = 1;
                    visited[i + 1][j] = true;
                }else{ 
                    dfs2(grid, i + 1, j);
                }
            }
            if (j - 1 >= 0 && !visited[i][j - 1]){ 
                if (grid[i][j - 1] == 0){ 
                    grid[i][j - 1] = 1;
                    visited[i][j - 1] = true;
                }else{ 
                    dfs2(grid, i, j - 1);
                }
            }
            if (j + 1 < m && !visited[i][j + 1]){ 
                if (grid[i][j + 1] == 0){ 
                    grid[i][j + 1] = 1;
                    visited[i][j + 1] = true;
                }else{ 
                    dfs2(grid, i, j + 1);
                }
            }
        }
    
        private void dfs1(int[][] grid, int i, int j) { 
            grid[i][j] = 2;
            if (i - 1 >= 0){ 
                if (grid[i - 1][j] == 1){ 
                    dfs1(grid, i - 1, j);
                }
            }
            if (i + 1 < n){ 
                if (grid[i + 1][j] == 1){ 
                    dfs1(grid, i + 1, j);
                }
            }
            if (j - 1 >= 0){ 
                if (grid[i][j - 1] == 1){ 
                    dfs1(grid, i, j - 1);
                }
            }
            if (j + 1 < m){ 
                if (grid[i][j + 1] == 1){ 
                    dfs1(grid, i, j + 1);
                }
            }
        }
    
    
        private int dfs(int[][] grid, int i, int j) { 
            if (grid[i][j] == 2){ 
                return 0;
            }
            visited[i][j] = true;
            int cur = 0;
            if (i - 1 >= 0 && !visited[i - 1][j]){ 
                if (grid[i - 1][j] == 0){ 
                    cur++;
                    set.add(index(i - 1, j));
                }else{ 
                    cur += dfs(grid, i - 1, j);
                }
            }
            if (i + 1 < n && !visited[i + 1][j]){ 
                if (grid[i + 1][j] == 0){ 
                    cur++;
                    set.add(index(i + 1 ,j));
                }else{ 
                    cur += dfs(grid, i + 1, j);
                }
            }
            if (j - 1 >= 0 && !visited[i][j - 1]){ 
                if (grid[i][j - 1] == 0){ 
                    cur++;
                    set.add(index(i, j - 1));
                }else{ 
                    cur += dfs(grid, i, j - 1);
                }
            }
            if (j + 1 < m && !visited[i][j + 1]){ 
                if (grid[i][j + 1] == 0){ 
                    cur++;
                    set.add(index(i, j + 1));
                }else{ 
                    cur += dfs(grid, i, j + 1);
                }
            }
            return cur;
        }
    
        private int index(int i, int j){ 
            return m * i + j;
        }
    }