Last updated on October 9th, 2024 at 06:22 pm
Here, We see Contain Virus LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Hash Table
Level of Question
Hard
Contain Virus LeetCode Solution
Table of Contents
Problem Statement
A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.
The world is modeled as an m x n binary grid isInfected, where isInfected[i][j] == 0 represents uninfected cells, and isInfected[i][j] == 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 (i.e., the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night). There will never be a tie.
Return the number of walls used to quarantine all the infected regions. If the world will become fully infected, return the number of walls used.
Example 1:
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: 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: 
On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained. 
Example 2:
Input: isInfected = [[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: 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]] Output: 13 Explanation: The region on the left only builds two new walls.
1. Contain Virus LeetCode Solution C++
int mp[2652], *zp[2652], zc[2652], step, mk;
int dfs(int *p) {
*p = 2;
int res = 0;
for (int *nb : {p-step, p-1, p+1, p+step}) {
int v = *nb;
if (v == mk || v > 1) continue;
if (v <= 0) *nb = mk, ++res; else res += dfs(nb);
}
return res;
}
int dfs2(int *p) {
*p = 1000;
int res = 0;
for (int *nb : {p-step, p-1, p+1, p+step}) {
int v = *nb;
if (v == 2) res += dfs2(nb); else if (v <= 0) ++res, *nb = 0;
}
return res;
}
void dfs3(int *p) {
*p = 1;
for (int *nb : {p-step, p-1, p+1, p+step}) {
int v = *nb;
if (v == 2) dfs3(nb); else if (v <= 0) *nb = 1;
}
}
class Solution {
public:
int containVirus(vector<vector<int>>& isInfected) {
step = isInfected[0].size() + 1; mk = 0;
{
int *p = mp+step;
fill(mp, p, 1000);
for (const auto &r : isInfected) {
for (int x : r) *p++ = x;
*p++ = 1000;
}
fill(p, p+step, 1000);
}
int *lo = mp+step, *hi = lo + step*isInfected.size(), res = 0;
while(1) {
int nb = 0;
for (int *p = lo; p != hi; ++p) if (*p == 1) zp[nb] = p, --mk, zc[nb++] = dfs(p);
if (nb == 0) break;
int best = 0;
for (int i = 1; i < nb; ++i) if (zc[i] > zc[best]) best = i;
if (!zc[best]) break;
res += dfs2(zp[best]);
for (int *p = lo; p != hi; ++p) if (*p == 2) dfs3(p);
}
return res;
}
};
2. Contain Virus LeetCode Solution Java
class Solution {
class Region {
Set<Integer> infected = new HashSet<>();
Set<Integer> unInfected = new HashSet<>();
int walls = 0;
}
public int containVirus(int[][] isInfected) {
int ans = 0;
int re = isInfected.length;
int ce = isInfected[0].length;
while (true) {
List<Region> holder = new ArrayList<>();
boolean[][] v = new boolean[re][ce];
for (int r = 0; r < re; r++) {
for (int c = 0; c < ce; c++) {
if (isInfected[r][c] == 1 && !v[r][c]) {
Region region = new Region();
getRegion(isInfected, region, re, ce, v, r, c);
holder.add(region);
}
}
}
int indexOfMaxUnInfected = 0;
int sizeOfMaxUnInfected = 0;
for (int i = 0; i < holder.size(); i++) {
Region region = holder.get(i);
if (region.unInfected.size() > sizeOfMaxUnInfected) {
sizeOfMaxUnInfected = region.unInfected.size();
indexOfMaxUnInfected = i;
}
}
if (holder.size() == 0) {
break;
}
Set<Integer> maxSet = holder.get(indexOfMaxUnInfected).infected;
for (int rowCol : maxSet) {
int r = rowCol / ce;
int c = rowCol % ce;
isInfected[r][c] = 2;
}
ans += holder.get(indexOfMaxUnInfected).walls;
for (int i = 0; i < holder.size(); i++) {
if (i == indexOfMaxUnInfected) {
continue;
}
Region region = holder.get(i);
Set<Integer> unInfected = region.unInfected;
for (int rowCol : unInfected) {
int r = rowCol / ce;
int c = rowCol % ce;
isInfected[r][c] = 1;
}
}
}
return ans;
}
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void getRegion(int[][] isInfected, Region region, int re, int ce,
boolean[][] v, int r, int c) {
if (r < 0 || c < 0 || r == re || c == ce || isInfected[r][c] == 2) {
return;
}
if (isInfected[r][c] == 1) {
if (v[r][c]) {
return;
}
region.infected.add(r * ce + c);
}
if (isInfected[r][c] == 0) {
region.unInfected.add(r * ce + c);
region.walls++;
return;
}
v[r][c] = true;
for (int[] dir : dirs) {
int nr = r + dir[0];
int nc = c + dir[1];
getRegion(isInfected, region, re, ce, v, nr, nc);
}
}
}3. Contain Virus LeetCode Solution JavaScript
var containVirus = function(isInfected) {
const R = isInfected.length
const C = isInfected[0].length
const DIRS = [[1,0],[0,1],[-1,0],[0,-1]]
let res = 0
while(true) {
const visited = new Set()
const pq = new Heap((a,b) => b.futureInfected.size - a.futureInfected.size)
for(let i = 0; i < R; i++) {
for(let j = 0; j < C; j++) {
if(!visited.has([i,j].join(',')) && isInfected[i][j]===1) {
const cluster = new Cluster()
dfs(i,j, cluster)
pq.add(cluster)
}
}
}
if(pq.size===0) return res
const top = pq.pop()[0] // {currInfected}
res += top.walls
for(const cell of top.currentInfected) {
const [row,col] = cell.split(',')
isInfected[row][col] = -1
}
while(pq.size) {
const top = pq.pop()[0] // {currInfected}
for(const cell of top.futureInfected) {
const [row,col] = cell.split(',')
isInfected[row][col] = 1
}
}
function dfs(r,c,cluster) {
if(r < 0 || c < 0 || r > R - 1 || c > C - 1) return
if(isInfected[r][c] ===-1) return
if(isInfected[r][c] === 0) {
cluster.walls++
cluster.futureInfected.add([r,c].join(','))
return
}
if(visited.has([r,c].join(','))) return
visited.add([r,c].join(','))
cluster.currentInfected.add([r,c].join(','))
for(const [rowDir, colDir] of DIRS) {
const nextRow = rowDir + r
const nextCol = colDir + c
dfs(nextRow, nextCol, cluster)
}
}
}
};
class Cluster {
constructor() {
this.walls = 0
this.futureInfected = new Set()
this.currentInfected = new Set()
}
}
class Heap {
constructor(cmpFn, array = []) {
this.name = cmpFn == undefined? 'min': 'custom';
this.cmpFn = cmpFn || this.internalCmpFn;
this.tree = [];
this.size = 0;
this.count = 0;
this.idxMap = new Map();
this.idxRevMap = new Map();
for(let value of array) {
this.add(value);
}
}
_left(idx) {
return 2 * idx + 1;
}
_right(idx) {
return 2 * idx + 2;
}
_parent(idx) {
return (idx - 1) / 2 >> 0;
}
_swap(i, j) {
let countI = this.idxMap.get(i);
let countJ = this.idxMap.get(j);
let idxI = this.idxRevMap.get(countI);
let idxJ = this.idxRevMap.get(countJ);
this.idxMap.set(i, countJ);
this.idxMap.set(j, countI);
this.idxRevMap.set(countI, j);
this.idxRevMap.set(countJ, i);
[this.tree[i], this.tree[j]] = [this.tree[j], this.tree[i]];
}
internalCmpFn(value1, value2) {
return value1 - value2;
}
_heapifyUp(idx) {
let parent = this._parent(idx);
while(parent != idx && this.cmpFn(this.tree[idx], this.tree[parent]) < 0) {
this._swap(idx, parent);
idx = parent;
parent = this._parent(idx);
}
}
add(value, count) {
count = count == undefined? this.count: count;
this.tree[this.size] = value;
this.idxMap.set(this.size, count);
this.idxRevMap.set(count, this.size);
let idx = this.size;
this._heapifyUp(idx);
this.size++;
this.count++;
}
heapify(idx) {
let left = this._left(idx);
let right = this._right(idx);
let current = idx;
if(left < this.size && this.cmpFn(this.tree[left], this.tree[idx]) < 0) {
current = left;
}
if(right < this.size && this.cmpFn(this.tree[right], this.tree[current]) < 0) {
current = right;
}
if(current != idx) {
this._swap(idx, current);
this.heapify(current);
}
}
pop() {
if(this.size == 0) {
return null;
}
let value = this.tree[0];
let count = this.idxMap.get(0);
this._swap(0, this.size - 1);
this.size--;
this.tree.length = this.size;
this.heapify(0);
this.idxRevMap.delete(count);
this.idxMap.delete(this.size);
return [value, count];
}
popAt(count) {
if(!this.idxRevMap.has(count) || this.size == 0) {
return null;
}
let idx = this.idxRevMap.get(count);
let value = this.tree[idx];
this._swap(idx, this.size - 1);
this.size--;
this.tree.length = this.size;
this.heapify(idx);
this._heapifyUp(idx);
this.idxRevMap.delete(count);
this.idxMap.delete(this.size);
return [value, count];
}
peek() {
return this.tree[0];
}
}4. Contain Virus LeetCode Solution Python
class Solution(object):
def containVirus(self, isInfected):
m, n = len(isInfected), len(isInfected[0])
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(i, j, visited):
if not (0 <= i < m and 0 <= j < n) or (i, j) in visited:
return set(), 0
if isInfected[i][j] == 2:
return set(), 0
elif isInfected[i][j] == 0:
return {(i, j)}, 1
visited.add((i, j))
infected, walls = set(), 0
for dx, dy in DIRECTIONS:
ni, nj = i + dx, j + dy
next_infected, next_walls = dfs(ni, nj, visited)
infected |= next_infected
walls += next_walls
return infected, walls
def quarantine(i, j):
if 0 <= i < m and 0 <= j < n and isInfected[i][j] == 1:
isInfected[i][j] = 2
for dx, dy in DIRECTIONS:
quarantine(i + dx, j + dy)
ans = 0
while True:
visited, regions = set(), []
for i in range(m):
for j in range(n):
if isInfected[i][j] == 1 and (i, j) not in visited:
infected, walls = dfs(i, j, visited)
if infected:
regions.append((infected, walls, (i, j)))
if not regions:
break
regions.sort(key=lambda x: (-len(x[0]), x[1]))
max_infected, max_walls, start = regions[0]
ans += max_walls
quarantine(*start)
for region in regions[1:]:
for i, j in region[0]:
isInfected[i][j] = 1
return ans