Question

749. 隔离病毒

English Version

题目描述

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

假设世界由 m x n 的二维矩阵 isInfected 组成， isInfected[i][j] == 0 表示该区域未感染病毒，而  isInfected[i][j] == 1 表示该区域已感染病毒。可以在任意 2 个相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。

每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且 保证唯一 。

你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。

 

示例 1：

输入: isInfected = [[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 个墙来隔离病毒区域。此时病毒已经被完全控制住了。

示例 2：

输入: isInfected = [[1,1,1],[1,0,1],[1,1,1]]
输出: 4
解释: 虽然只保存了一个小区域，但却有四面墙。
注意，防火墙只建立在两个不同区域的共享边界上。

示例 3:

输入: isInfected = [[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 个防火墙。

 

提示:

• m == isInfected.length
• n == isInfected[i].length
• 1 <= m, n <= 50
• isInfected[i][j] is either 0 or 1
• 在整个描述的过程中，总有一个相邻的病毒区域，它将在下一轮 严格地感染更多未受污染的方块 

 

解法

方法一：DFS 暴力模拟

DFS 找到每个病毒区域 areas[i]，同时记录每个区域边界节点 boundaries[i] 以及周长 c[i]。

接着对威胁最大的病毒区域进行隔离，累加所需的防火墙数量。

剩余的病毒区域向外感染一个区域。

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

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);
        }
      }
    }
  }
}

class Solution {
public:
  const vector<int> dirs = {-1, 0, 1, 0, -1};
  vector<int> c;
  vector<vector<int>> areas;
  vector<unordered_set<int>> boundaries;
  vector<vector<int>> infected;
  vector<vector<bool>> vis;
  int m;
  int n;

  int containVirus(vector<vector<int>>& isInfected) {
    infected = isInfected;
    m = infected.size();
    n = infected[0].size();
    vis.assign(m, vector<bool>(n));
    int ans = 0;
    while (1) {
      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) vis[i][j] = 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.push_back(0);
            areas.push_back({});
            boundaries.push_back({});
            dfs(i, j);
          }
        }
      }
      if (areas.empty()) break;
      int idx = getMax();
      ans += c[idx];
      for (int t = 0; t < areas.size(); ++t) {
        if (t == idx) {
          for (int v : areas[t]) {
            int i = v / n, j = v % n;
            infected[i][j] = -1;
          }
        } else {
          for (int v : areas[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;
  }

  int getMax() {
    int idx = 0;
    int mx = boundaries[0].size();
    for (int i = 1; i < boundaries.size(); ++i) {
      int t = boundaries[i].size();
      if (mx < t) {
        mx = t;
        idx = i;
      }
    }
    return idx;
  }

  void dfs(int i, int j) {
    vis[i][j] = true;
    areas.back().push_back(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.back() += 1;
          boundaries.back().insert(x * n + y);
        }
      }
    }
  }
};

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
}