You are given a 2D grid representing a laboratory where some cells are infected by a virus, and others are uninfected. The grid is a matrix of integers, where:
grid[i][j] == 1 means the cell at row i and column j is infected.grid[i][j] == 0 means the cell is uninfected.grid[i][j] == -1 means the cell is contained by a wall and cannot be infected anymore.
The problem is about simulating the spread of a virus in a grid, with the added complexity that we can contain one region per day. At first glance, a brute-force approach might be to simulate all possible wall placements, but this would be too slow for large grids.
Instead, we should focus on the greedy strategy described in the prompt: always contain the most "dangerous" region (the one that would infect the most new cells). This means:
We can break down the solution into the following steps:
-1 (contained).1).
Sample 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]
]
Step 1: Identify all infected regions:
Brute-force Approach:
The key insight is to use a greedy approach: always contain the region that threatens to infect the most new cells. By systematically identifying regions, tracking their potential spread, and simulating the virus, we efficiently minimize the number of walls needed. The use of BFS/DFS, sets for tracking, and careful simulation makes the solution both clear and efficient.
class Solution:
def containVirus(self, grid):
from collections import deque, defaultdict
m, n = len(grid), len(grid[0])
total_walls = 0
def neighbors(r, c):
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n:
yield nr, nc
while True:
visited = [[False]*n for _ in range(m)]
regions = []
frontiers = []
walls_needed = []
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and not visited[r][c]:
region = []
frontier = set()
walls = 0
queue = deque()
queue.append((r, c))
visited[r][c] = True
while queue:
x, y = queue.popleft()
region.append((x, y))
for nx, ny in neighbors(x, y):
if grid[nx][ny] == 0:
frontier.add((nx, ny))
walls += 1
elif grid[nx][ny] == 1 and not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny))
regions.append(region)
frontiers.append(frontier)
walls_needed.append(walls)
if not regions:
break
# Find the region with the max frontier
max_idx = -1
max_frontier = 0
for i, frontier in enumerate(frontiers):
if len(frontier) > max_frontier:
max_frontier = len(frontier)
max_idx = i
if max_frontier == 0:
break
# Build walls for the most threatening region
total_walls += walls_needed[max_idx]
for x, y in regions[max_idx]:
grid[x][y] = -1
# Spread virus for other regions
for i, region in enumerate(regions):
if i == max_idx:
continue
for x, y in frontiers[i]:
grid[x][y] = 1
return total_walls
class Solution {
public:
int containVirus(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int totalWalls = 0;
vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (true) {
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<vector<pair<int,int>>> regions;
vector<set<pair<int,int>>> frontiers;
vector<int> wallsNeeded;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (grid[r][c] == 1 && !visited[r][c]) {
vector<pair<int,int>> region;
set<pair<int,int>> frontier;
int walls = 0;
queue<pair<int,int>> q;
q.push({r, c});
visited[r][c] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
region.push_back({x, y});
for (auto& d : dirs) {
int nx = x + d.first, ny = y + d.second;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 0) {
frontier.insert({nx, ny});
walls++;
} else if (grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
regions.push_back(region);
frontiers.push_back(frontier);
wallsNeeded.push_back(walls);
}
}
}
if (regions.empty()) break;
int maxIdx = -1, maxFrontier = 0;
for (int i = 0; i < frontiers.size(); ++i) {
if (frontiers[i].size() > maxFrontier) {
maxFrontier = frontiers[i].size();
maxIdx = i;
}
}
if (maxFrontier == 0) break;
totalWalls += wallsNeeded[maxIdx];
for (auto& cell : regions[maxIdx]) {
grid[cell.first][cell.second] = -1;
}
for (int i = 0; i < regions.size(); ++i) {
if (i == maxIdx) continue;
for (auto& cell : frontiers[i]) {
grid[cell.first][cell.second] = 1;
}
}
}
return totalWalls;
}
};
class Solution {
public int containVirus(int[][] grid) {
int m = grid.length, n = grid[0].length;
int totalWalls = 0;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
while (true) {
boolean[][] visited = new boolean[m][n];
List<List<int[]>> regions = new ArrayList<>();
List<Set<String>> frontiers = new ArrayList<>();
List<Integer> wallsNeeded = new ArrayList<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 1 && !visited[r][c]) {
List<int[]> region = new ArrayList<>();
Set<String> frontier = new HashSet<>();
int walls = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{r, c});
visited[r][c] = true;
while (!q.isEmpty()) {
int[] cell = q.poll();
region.add(cell);
for (int[] d : dirs) {
int nx = cell[0] + d[0], ny = cell[1] + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] == 0) {
frontier.add(nx + "," + ny);
walls++;
} else if (grid[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
}
}
}
}
regions.add(region);
frontiers.add(frontier);
wallsNeeded.add(walls);
}
}
}
if (regions.isEmpty()) break;
int maxIdx = -1, maxFrontier = 0;
for (int i = 0; i < frontiers.size(); i++) {
if (frontiers.get(i).size() > maxFrontier) {
maxFrontier = frontiers.get(i).size();
maxIdx = i;
}
}
if (maxFrontier == 0) break;
totalWalls += wallsNeeded.get(maxIdx);
for (int[] cell : regions.get(maxIdx)) {
grid[cell[0]][cell[1]] = -1;
}
for (int i = 0; i < regions.size(); i++) {
if (i == maxIdx) continue;
for (String s : frontiers.get(i)) {
String[] parts = s.split(",");
int x = Integer.parseInt(parts[0]);
int y = Integer.parseInt(parts[1]);
grid[x][y] = 1;
}
}
}
return totalWalls;
}
}
var containVirus = function(grid) {
let m = grid.length, n = grid[0].length;
let dirs = [[-1,0],[1,0],[0,-1],[0,1]];
let totalWalls = 0;
while (true) {
let visited = Array.from({length: m}, () => Array(n).fill(false));
let regions = [], frontiers = [], wallsNeeded = [];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (grid[r][c] === 1 && !visited[r][c]) {
let region = [], frontier = new Set(), walls = 0;
let queue = [[r, c]];
visited[r][c] = true;
while (queue.length) {
let [x, y] = queue.shift();
region.push([x, y]);
for (let [dx, dy] of dirs) {
let nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] === 0) {
frontier.add(nx + ',' + ny);
walls++;
} else if (grid[nx][ny] === 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.push([nx, ny]);
}
}
}
}
regions.push(region);
frontiers.push(frontier);
wallsNeeded.push(walls);
}
}
}
if (regions.length === 0) break;
let maxIdx = -1, maxFrontier = 0;
for (let i = 0; i < frontiers.length; i++) {
if (frontiers[i].size > maxFrontier) {
maxFrontier = frontiers[i].size;
maxIdx = i;
}
}
if (maxFrontier === 0) break;
totalWalls += wallsNeeded[maxIdx];
for (let [x, y] of regions[maxIdx]) {
grid[x][y] = -1;
}
for (let i = 0; i < regions.length; i++) {
if (i === maxIdx) continue;
for (let s of frontiers[i]) {
let [nx, ny] = s.split(',').map(Number);
grid[nx][ny] = 1;
}
}
}
return totalWalls;
};