Contain Virus
Problem
Given a grid where 1 denotes infected cells and 0 healthy ones, each day quarantine the region threatening the most uninfected cells by building walls around it, then let remaining regions spread to all adjacent 0s. Return the total walls used until no spread remains.
Input
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]]Output
10Two virus regions exist; over two days a total of 10 walls are built to contain them.
def containVirus(grid):
m, n = len(grid), len(grid[0])
walls_total = 0
while True:
regions, frontiers, perims = [], [], []
seen = [[False]*n for _ in range(m)]
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and not seen[r][c]:
region, frontier, perim = [], set(), 0
stack = [(r, c)]; seen[r][c] = True
while stack:
x, y = stack.pop(); region.append((x, y))
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] == 1 and not seen[nx][ny]:
seen[nx][ny] = True; stack.append((nx, ny))
elif grid[nx][ny] == 0:
frontier.add((nx, ny)); perim += 1
regions.append(region); frontiers.append(frontier); perims.append(perim)
if not regions: return walls_total
idx = max(range(len(regions)), key=lambda i: len(frontiers[i]))
walls_total += perims[idx]
for i, region in enumerate(regions):
if i == idx:
for x, y in region: grid[x][y] = 2
else:
for x, y in frontiers[i]: grid[x][y] = 1function containVirus(grid) {
const m = grid.length, n = grid[0].length;
let walls = 0;
while (true) {
const regions = [], frontiers = [], perims = [];
const seen = Array.from({length: m}, () => Array(n).fill(false));
for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) {
if (grid[r][c] === 1 && !seen[r][c]) {
const region = [], frontier = new Set(); let perim = 0;
const stack = [[r, c]]; seen[r][c] = true;
while (stack.length) {
const [x, y] = stack.pop(); region.push([x, y]);
for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (grid[nx][ny] === 1 && !seen[nx][ny]) { seen[nx][ny] = true; stack.push([nx, ny]); }
else if (grid[nx][ny] === 0) { frontier.add(nx * n + ny); perim++; }
}
}
regions.push(region); frontiers.push(frontier); perims.push(perim);
}
}
if (!regions.length) return walls;
let idx = 0;
for (let i = 1; i < regions.length; i++) if (frontiers[i].size > frontiers[idx].size) idx = i;
walls += perims[idx];
for (let i = 0; i < regions.length; i++) {
if (i === idx) for (const [x, y] of regions[i]) grid[x][y] = 2;
else for (const f of frontiers[i]) grid[Math.floor(f / n)][f % n] = 1;
}
}
}class Solution {
int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
public int containVirus(int[][] grid) {
int m = grid.length, n = grid[0].length, walls = 0;
while (true) {
List<List<int[]>> regions = new ArrayList<>();
List<Set<Integer>> frontiers = new ArrayList<>();
List<Integer> perims = new ArrayList<>();
boolean[][] seen = new boolean[m][n];
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && !seen[r][c]) {
List<int[]> reg = new ArrayList<>(); Set<Integer> fr = new HashSet<>(); int per = 0;
Deque<int[]> st = new ArrayDeque<>(); st.push(new int[]{r,c}); seen[r][c] = true;
while (!st.isEmpty()) {
int[] p = st.pop(); reg.add(p);
for (int[] d : DIRS) {
int nx = p[0]+d[0], ny = p[1]+d[1];
if (nx<0||ny<0||nx>=m||ny>=n) continue;
if (grid[nx][ny]==1 && !seen[nx][ny]) { seen[nx][ny]=true; st.push(new int[]{nx,ny}); }
else if (grid[nx][ny]==0) { fr.add(nx*n+ny); per++; }
}
}
regions.add(reg); frontiers.add(fr); perims.add(per);
}
}
if (regions.isEmpty()) return walls;
int idx = 0;
for (int i = 1; i < regions.size(); i++) if (frontiers.get(i).size() > frontiers.get(idx).size()) idx = i;
walls += perims.get(idx);
for (int i = 0; i < regions.size(); i++) {
if (i == idx) for (int[] p : regions.get(i)) grid[p[0]][p[1]] = 2;
else for (int f : frontiers.get(i)) grid[f/n][f%n] = 1;
}
}
}
}class Solution {
public:
int containVirus(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), walls = 0;
vector<pair<int,int>> DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
while (true) {
vector<vector<pair<int,int>>> regions;
vector<set<int>> frontiers; vector<int> perims;
vector<vector<bool>> seen(m, vector<bool>(n, false));
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && !seen[r][c]) {
vector<pair<int,int>> reg; set<int> fr; int per = 0;
vector<pair<int,int>> st = {{r,c}}; seen[r][c] = true;
while (!st.empty()) {
auto [x,y] = st.back(); st.pop_back(); reg.push_back({x,y});
for (auto [dx,dy] : DIRS) {
int nx=x+dx, ny=y+dy;
if (nx<0||ny<0||nx>=m||ny>=n) continue;
if (grid[nx][ny]==1 && !seen[nx][ny]) { seen[nx][ny]=true; st.push_back({nx,ny}); }
else if (grid[nx][ny]==0) { fr.insert(nx*n+ny); per++; }
}
}
regions.push_back(reg); frontiers.push_back(fr); perims.push_back(per);
}
}
if (regions.empty()) return walls;
int idx = 0;
for (int i = 1; i < (int)regions.size(); i++) if (frontiers[i].size() > frontiers[idx].size()) idx = i;
walls += perims[idx];
for (int i = 0; i < (int)regions.size(); i++) {
if (i == idx) for (auto [x,y] : regions[i]) grid[x][y] = 2;
else for (int f : frontiers[i]) grid[f/n][f%n] = 1;
}
}
}
};Explanation
This is a day-by-day simulation. Each day we find all the separate virus regions, build a wall around the most dangerous one, and then let the others spread. We repeat until nothing can spread anymore.
Every day we flood-fill (DFS) over the infected cells to discover each region. For each region we collect its frontier (the distinct healthy cells it would infect next) and its perim (the number of wall segments needed to seal it off — adjacent healthy cells counted with multiplicity).
The region with the largest frontier threatens the most new cells, so we quarantine it by marking those cells as 2 and add its perim to the wall total. All other regions then spread, turning their frontier cells into new infected 1s.
When a pass finds no regions left that can spread, we return the accumulated wall count. In the sample grid two regions appear, and over two days a total of 10 walls are built to contain the threat.