749. Contain Virus

749. Contain Virus

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region – the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: 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]]Output: 10Explanation:There are 2 contaminated regions.On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:[[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]]On the second day, add 5

Example 2:

Input: grid = [[1,1,1], [1,0,1], [1,1,1]]Output: 4Explanation: Even though there is only one cell saved, there are 4

Example 3:

Input: 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]]Output: 13

Note: The number of rows and columns of grid will each be in the range [1, 50]. Each grid[i][j] will be either 0 or 1. Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

class Solution { Set seen; List> regions; List> frontiers; List perimeters; int[][] grid; int R, C; int[] dr = new int[]{-1, 1, 0, 0}; int[] dc = new int[]{0, 0, -1, 1}; public int containVirus(int[][] grid) { this.grid = grid; R = grid.length; C = grid[0].length; int ans = 0; while (true) { seen = new HashSet(); regions = new ArrayList(); frontiers = new ArrayList(); perimeters = new ArrayList(); for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) { if (grid[r][c] == 1 && !seen.contains(r*C + c)) { regions.add(new HashSet()); frontiers.add(new HashSet()); perimeters.add(0); dfs(r, c); } } } if (regions.isEmpty()) break; int triageIndex = 0; for (int i = 0; i < frontiers.size(); ++i) { if (frontiers.get(triageIndex).size() < frontiers.get(i).size()) triageIndex = i; } ans += perimeters.get(triageIndex); for (int i = 0; i < regions.size(); ++i) { if (i == triageIndex) { for (int code: regions.get(i)) grid[code / C][code % C] = -1; } else { for (int code: regions.get(i)) { int r = code / C, c = code % C; for (int k = 0; k < 4; ++k) { int nr = r + dr[k], nc = c + dc[k]; if (nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 0) grid[nr][nc] = 1; } } } } } return ans; } public void dfs(int r, int c) { if (!seen.contains(r*C + c)) { seen.add(r*C + c); int N = regions.size(); regions.get(N - 1).add(r*C + c); for (int k = 0; k < 4; ++k) { int nr = r + dr[k], nc = c + dc[k]; if (nr >= 0 && nr < R && nc >= 0 && nc < C) { if (grid[nr][nc] == 1) { dfs(nr, nc); } else if (grid[nr][nc] == 0){ frontiers.get(N - 1).add(nr*C + nc); perimeters.set(N - 1, perimeters.get(N - 1) + 1); } } } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。