class Solution:
def containVirus(self, isInfected: List[List[int]]) -> int:
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
m, n = len(isInfected), len(isInfected[0])
ans = 0
while True:
neighbors, firewalls = list(), list()
for i in range(m):
for j in range(n):
if isInfected[i][j] == 1:
q = deque([(i, j)])
neighbor = set()
firewall, idx = 0, len(neighbors) + 1
isInfected[i][j] = -idx
while q:
x, y = q.popleft()
for d in range(4):
nx, ny = x + dirs[d][0], y + dirs[d][1]
if 0 <= nx < m and 0 <= ny < n:
if isInfected[nx][ny] == 1:
q.append((nx, ny))
isInfected[nx][ny] = -idx
elif isInfected[nx][ny] == 0:
firewall += 1
neighbor.add((nx, ny))
neighbors.append(neighbor)
firewalls.append(firewall)
if not neighbors:
break
idx = 0
for i in range(1, len(neighbors)):
if len(neighbors[i]) > len(neighbors[idx]):
idx = i
ans += firewalls[idx]
for i in range(m):
for j in range(n):
if isInfected[i][j] < 0:
if isInfected[i][j] != -idx - 1:
isInfected[i][j] = 1
else:
isInfected[i][j] = 2
for i, neighbor in enumerate(neighbors):
if i != idx:
for x, y in neighbor:
isInfected[x][y] = 1
if len(neighbors) == 1:
break
return ans
func containVirus(isInfected [][]int) int {
m, n := len(isInfected), len(isInfected[0])
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
max := func(boundaries []map[int]bool) int {
idx := 0
mx := len(boundaries[0])
for i, v := range boundaries {
t := len(v)
if mx < t {
mx = t
idx = i
}
}
return idx
}
for {
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
areas := []map[int]bool{}
boundaries := []map[int]bool{}
c := []int{}
var dfs func(i, j int)
dfs = func(i, j int) {
vis[i][j] = true
idx := len(areas) - 1
areas[idx][i*n+j] = true
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n {
if isInfected[x][y] == 1 && !vis[x][y] {
dfs(x, y)
} else if isInfected[x][y] == 0 {
c[idx]++
boundaries[idx][x*n+y] = true
}
}
}
}
for i, row := range isInfected {
for j, v := range row {
// 找到每块连通的病毒区域
if v == 1 && !vis[i][j] {
areas = append(areas, map[int]bool{})
boundaries = append(boundaries, map[int]bool{})
c = append(c, 0)
dfs(i, j)
}
}
}
if len(areas) == 0 {
break
}
// 威胁最大的区域
idx := max(boundaries)
// 累加防火墙
ans += c[idx]
for t, area := range areas {
if t == idx {
// 此区域已成功堵住
for v := range area {
i, j := v/n, v%n
isInfected[i][j] = -1
}
} else {
// 向外感染一个区域
for v := range area {
i, j := v/n, v%n
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && isInfected[x][y] == 0 {
isInfected[x][y] = 1
}
}
}
}
}
}
return ans
}
class Solution {
private static final int[] DIRS = {-1, 0, 1, 0, -1};
private List<Integer> c = new ArrayList<>();
private List<List<Integer>> areas = new ArrayList<>();
private List<Set<Integer>> boundaries = new ArrayList<>();
private int[][] infected;
private boolean[][] vis;
private int m;
private int n;
public int containVirus(int[][] isInfected) {
infected = isInfected;
m = infected.length;
n = infected[0].length;
vis = new boolean[m][n];
int ans = 0;
while (true) {
for (boolean[] row : vis) {
Arrays.fill(row, false);
}
c.clear();
areas.clear();
boundaries.clear();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 找到每块连通的病毒区域
if (infected[i][j] == 1 && !vis[i][j]) {
c.add(0);
areas.add(new ArrayList<>());
boundaries.add(new HashSet<>());
dfs(i, j);
}
}
}
if (areas.isEmpty()) {
break;
}
// 威胁最大的区域
int idx = max(boundaries);
// 累加防火墙
ans += c.get(idx);
for (int t = 0; t < areas.size(); ++t) {
if (t == idx) {
// 此区域已成功堵住
for (int v : areas.get(t)) {
int i = v / n, j = v % n;
infected[i][j] = -1;
}
} else {
// 向外感染一个区域
for (int v : areas.get(t)) {
int i = v / n, j = v % n;
for (int k = 0; k < 4; ++k) {
int x = i + DIRS[k], y = j + DIRS[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && infected[x][y] == 0) {
infected[x][y] = 1;
}
}
}
}
}
}
return ans;
}
private int max(List<Set<Integer>> boundaries) {
int idx = 0;
int mx = boundaries.get(0).size();
for (int i = 1; i < boundaries.size(); ++i) {
int t = boundaries.get(i).size();
if (mx < t) {
mx = t;
idx = i;
}
}
return idx;
}
private void dfs(int i, int j) {
vis[i][j] = true;
int idx = areas.size() - 1;
areas.get(idx).add(i * n + j);
for (int k = 0; k < 4; ++k) {
int x = i + DIRS[k], y = j + DIRS[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (infected[x][y] == 1 && !vis[x][y]) {
dfs(x, y);
} else if (infected[x][y] == 0) {
c.set(idx, c.get(idx) + 1);
boundaries.get(idx).add(x * n + y);
}
}
}
}
}
# dfs暴力模拟
class Solution:
def containVirus(self, isInfected: List[List[int]]) -> int:
def dfs(i, j):
vis[i][j] = True
areas[-1].append((i, j))
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if isInfected[x][y] == 1 and not vis[x][y]:
dfs(x, y)
elif isInfected[x][y] == 0:
c[-1] += 1
boundaries[-1].add((x, y))
m, n = len(isInfected), len(isInfected[0])
ans = 0
while 1:
vis = [[False] * n for _ in range(m)]
areas = []
c = []
boundaries = []
for i, row in enumerate(isInfected):
for j, v in enumerate(row):
# 找到每块连通的病毒区域
if v == 1 and not vis[i][j]:
areas.append([])
boundaries.append(set())
c.append(0)
dfs(i, j)
if not areas:
break
# 威胁最大的区域
idx = boundaries.index(max(boundaries, key=len))
# 累加防火墙
ans += c[idx]
for k, area in enumerate(areas):
if k == idx:
# 此区域已成功堵住
for i, j in area:
isInfected[i][j] = -1
else:
# 向外感染一个区域
for i, j in area:
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and isInfected[x][y] == 0:
isInfected[x][y] = 1
return ans
第二天，在右侧添加 5 个墙来隔离病毒区域。此时病毒已经被完全控制住了。
