The "Minimum Time For K Virus Variants to Spread" problem asks you to determine the minimum number of minutes needed for k different virus variants to spread and occupy all cells in a given grid. The grid is represented as a 2D matrix where each cell can be empty, a wall, or a potential virus starting point. You are allowed to choose k starting cells (from all possible virus sources), and from there, the virus spreads to adjacent cells (up, down, left, right) each minute. The objective is to select the optimal k starting points so that the entire grid is infected in the least time possible.
1) block the virus from spreading.0) need to be infected.k virus sources to activate.-1.
At first glance, this problem resembles common grid-based spread problems, such as "rotting oranges" or "shortest path in a maze." The brute-force idea is to try every possible combination of k starting virus positions and simulate the spread for each, then keep the minimum time. However, with many virus sources, the number of combinations can be huge, making brute-force infeasible.
We need a way to efficiently simulate the spread from multiple sources and to check all combinations of k virus positions. Breadth-First Search (BFS) is ideal for simulating simultaneous spread, as it naturally models "wavefront" expansion from multiple points. The challenge is efficiently handling all possible combinations and quickly determining if a configuration can infect the entire grid.
Thus, the key shifts are:
k starting positions from the list of virus sources.
-1.
BFS is chosen because it efficiently models simultaneous spread and ensures the minimum time to reach each cell. Combinations are necessary because any subset of virus sources could be optimal.
Sample Input:
grid = [
[2, 0, 1],
[0, 0, 0],
[1, 0, 2]
]
k = 2
Step-by-step:
1. Only one way to choose 2 virus sources: (0,0) and (2,2).
2. At time 0, both (0,0) and (2,2) are infected.
3. At time 1, virus spreads to adjacent empty cells.
4. Continue BFS until all empty cells are infected.
5. The last empty cell is infected at minute 3.
6. Return 3.
v virus sources, there are C(v, k) combinations. For each, BFS on an n x n grid is O(n^2). Total: O(C(v, k) * n^2).
O(n^2) space for the queue and visited set per run.
This problem combines combinatorics (choosing virus sources) with grid BFS simulation. The main insight is that BFS from multiple sources models simultaneous spread efficiently, and we must try all possible starting configurations to guarantee the minimum time. The solution is elegant because it leverages classic BFS and combinatorics in a straightforward, modular way.
from collections import deque
from itertools import combinations
def minTimeToSpread(grid, k):
n = len(grid)
virus = []
empty = 0
for i in range(n):
for j in range(n):
if grid[i][j] == 2:
virus.append((i, j))
elif grid[i][j] == 0:
empty += 1
if empty == 0:
return 0
ans = float('inf')
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
for comb in combinations(virus, k):
visited = [[-1]*n for _ in range(n)]
q = deque()
for x, y in comb:
visited[x][y] = 0
q.append((x, y))
cnt = 0
max_time = 0
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x+dx, y+dy
if 0<=nx<n and 0<=ny<n:
if grid[nx][ny] != 1 and visited[nx][ny] == -1:
visited[nx][ny] = visited[x][y] + 1
q.append((nx, ny))
if grid[nx][ny] == 0:
cnt += 1
max_time = visited[nx][ny]
if cnt == empty:
ans = min(ans, max_time)
return ans if ans != float('inf') else -1
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int minTimeToSpread(vector<vector<int>>& grid, int k) {
int n = grid.size();
vector<pair<int,int>> virus;
int empty = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (grid[i][j] == 2) virus.push_back({i,j});
else if (grid[i][j] == 0) empty++;
}
}
if (empty == 0) return 0;
int ans = INT_MAX;
vector<int> idx(virus.size());
fill(idx.end()-k, idx.end(), 1);
vector<int> dx = {-1,1,0,0}, dy = {0,0,-1,1};
do {
vector<vector<int>> visited(n, vector<int>(n, -1));
queue<pair<int,int>> q;
for (int i=0; i<virus.size(); ++i) {
if (idx[i]) {
visited[virus[i].first][virus[i].second] = 0;
q.push(virus[i]);
}
}
int cnt = 0, max_time = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int d=0; d<4; ++d) {
int nx = x+dx[d], ny = y+dy[d];
if (nx<0 || nx>=n || ny<0 || ny>=n) continue;
if (grid[nx][ny]!=1 && visited[nx][ny]==-1) {
visited[nx][ny] = visited[x][y]+1;
q.push({nx,ny});
if (grid[nx][ny]==0) {
cnt++;
max_time = visited[nx][ny];
}
}
}
}
if (cnt==empty) ans = min(ans, max_time);
} while (next_permutation(idx.begin(), idx.end()));
return ans==INT_MAX ? -1 : ans;
}
import java.util.*;
public class Solution {
public int minTimeToSpread(int[][] grid, int k) {
int n = grid.length;
List<int[]> virus = new ArrayList<>();
int empty = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (grid[i][j]==2) virus.add(new int[]{i, j});
else if (grid[i][j]==0) empty++;
}
}
if (empty==0) return 0;
int ans = Integer.MAX_VALUE;
int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
List<int[]> comb = new ArrayList<>();
combine(virus, comb, 0, k, new ArrayList<>(), grid, empty, ans, dx, dy, n);
return ans==Integer.MAX_VALUE ? -1 : ans;
}
void combine(List<int[]> virus, List<int[]> comb, int start, int k, List<int[]> curr, int[][] grid, int empty, int ans, int[] dx, int[] dy, int n) {
if (curr.size()==k) {
int time = bfs(curr, grid, empty, dx, dy, n);
if (time!=-1 && time<ans) ans = time;
return;
}
for (int i=start; i<virus.size(); ++i) {
curr.add(virus.get(i));
combine(virus, comb, i+1, k, curr, grid, empty, ans, dx, dy, n);
curr.remove(curr.size()-1);
}
}
int bfs(List<int[]> starts, int[][] grid, int empty, int[] dx, int[] dy, int n) {
int[][] visited = new int[n][n];
for (int[] row : visited) Arrays.fill(row, -1);
Queue<int[]> q = new LinkedList<>();
for (int[] s : starts) {
visited[s[0]][s[1]] = 0;
q.offer(new int[]{s[0], s[1]});
}
int cnt = 0, max_time = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1];
for (int d=0; d<4; ++d) {
int nx = x+dx[d], ny = y+dy[d];
if (nx<0 || nx>=n || ny<0 || ny>=n) continue;
if (grid[nx][ny]!=1 && visited[nx][ny]==-1) {
visited[nx][ny] = visited[x][y]+1;
q.offer(new int[]{nx, ny});
if (grid[nx][ny]==0) {
cnt++;
max_time = visited[nx][ny];
}
}
}
}
return cnt==empty ? max_time : -1;
}
}
function minTimeToSpread(grid, k) {
const n = grid.length;
const virus = [];
let empty = 0;
for (let i=0; i<n; ++i) {
for (let j=0; j<n; ++j) {
if (grid[i][j] === 2) virus.push([i,j]);
else if (grid[i][j] === 0) empty++;
}
}
if (empty === 0) return 0;
let ans = Infinity;
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
function* combinations(arr, k, start=0, curr=[]) {
if (curr.length === k) yield curr.slice();
else for (let i=start; i<arr.length; ++i) {
curr.push(arr[i]);
yield* combinations(arr, k, i+1, curr);
curr.pop();
}
}
for (const comb of combinations(virus, k)) {
const visited = Array.from({length: n}, () => Array(n).fill(-1));
const q = [];
for (const [x, y] of comb) {
visited[x][y] = 0;
q.push([x, y]);
}
let cnt = 0, max_time = 0;
let head = 0;
while (head < q.length) {
const [x, y] = q[head++];
for (const [dx, dy] of dirs) {
const nx = x+dx, ny = y+dy;
if (nx>=0 && nx<n && ny>=0 && ny<n) {
if (grid[nx][ny] !== 1 && visited[nx][ny] === -1) {
visited[nx][ny] = visited[x][y] + 1;
q.push([nx, ny]);
if (grid[nx][ny] === 0) {
cnt++;
max_time = visited[nx][ny];
}
}
}
}
}
if (cnt === empty) ans = Math.min(ans, max_time);
}
return ans === Infinity ? -1 : ans;
}