# LWC 63: 749. Contain Virus

### Problem:

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: 10 Explanation: 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 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = [[1,1,1], [1,0,1], [1,1,1]] Output: 4 Explanation: Even though there is only one cell saved, there are 4 walls built. Notice that walls are only built on the shared boundary of two different cells.

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 Explanation: The region on the left only builds two new walls.

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.

Java版本：

```public class Solution {

Set<Integer> vis;
List<Set<Integer>> frontiers;
List<Set<Integer>> regions;
List<Integer> perimeters;
int[][] grid;
int n, m;

int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};

public int containVirus(int[][] grid) {
this.grid = grid;
n = grid.length;
m = grid[0].length;
int ans = 0;
while (true) {
vis = new HashSet<>();
frontiers = new ArrayList<>();
regions = new ArrayList<>();
perimeters = new ArrayList<>();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] ==1 && !vis.contains(i * m + j)) {
dfs(i, j);
}
}
}

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 / m][code % m] = -1;
} else {
for (int code: regions.get(i)) {
int r = code / m, c = code % m;
for (int[] d : dir) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0)
grid[nr][nc] = 1;
}
}
}
}
}

return ans;
}

public void dfs(int r, int c) {
if (!vis.contains(r * m + c)) {
int N = regions.size();
regions.get(N - 1).add(r * m + c);
for (int[] d : dir) {
int nr = d[0] + r;
int nc = d[1] + c;
if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
if (grid[nr][nc] == 1) {
dfs(nr, nc);
}
else if (grid[nr][nc] == 0){
frontiers.get(N - 1).add(nr * m + nc);
perimeters.set(N - 1, perimeters.get(N - 1) + 1);
}
}
}
}
}

}```

Python版本：

```class Solution(object):
def containVirus(self, grid):
R, C = len(grid), len(grid[0])
def neighbors(r, c):
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc

def dfs(r, c):
if (r, c) not in seen:
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
dfs(nr, nc)
elif grid[nr][nc] == 0:
perimeters[-1] += 1

ans = 0
while True:
#Find all regions, with associated frontiers and perimeters.
seen = set()
regions = []
frontiers = []
perimeters = []
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val == 1 and (r, c) not in seen:
regions.append(set())
frontiers.append(set())
perimeters.append(0)
dfs(r, c)

if not regions: break

triage_index = frontiers.index(max(frontiers, key = len))
ans += perimeters[triage_index]

for i, reg in enumerate(regions):
if i == triage_index:
for r, c in reg:
grid[r][c] = -1
else:
for r, c in reg:
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 0:
grid[nr][nc] = 1

return ans```

0 条评论

## 相关文章

### HDU-1054 Strategic Game(树形DP)

Strategic Game Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32...

3188

### HDUOJ -----1686

Oulipo Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

2857

### LWC 62：743. Network Delay Time

LWC 62：743. Network Delay Time 传送门：743. Network Delay Time Problem: There are N...

2138

### POJ-1125 Stockbroker Grapevine

Stockbroker Grapevine Time Limit: 1000MS Memory Limit: 10000K Total Sub...

2884

### Leetcode 169 Majority Element

Given an array of size n, find the majority element. The majority element is th...

1709

### BZOJ1468: Tree

Description 给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K Input N（n<=40000） 接下来n-1行边描...

3139

2866

### hdu 4034 Graph (floyd的深入理解)

Graph Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Jav...

34211

3146

### 3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

3158