Virus Spread
National Olympiad — Regional round
Submission name: viruses.cpp
Problem summary
In an n-by-m grid, k initially infected cells spread infection to their four orthogonal neighbors every unit of time, simultaneously. Find when every cell is infected.
Input
n m, then k and k pairs of 1-based row and column coordinates.
Output
The required number of time units.
Constraints
1 ≤ n,m ≤ 3000; 1 ≤ k ≤ 10; coordinates lie inside the grid.
Worked example
An independently prepared example for this explanation.
Input
3 3 1 2 2
Output
2
Solution analysis
- For each cell compute its minimum Manhattan distance to the initial infected cells.
- The largest such minimum is the last infection time. This avoids allocating a queue for nine million cells.
Why it works
An infection needs at least Manhattan distance to reach a cell, and a shortest grid path achieves that time. The first arriving infection determines each cell’s time.
Complexity: O(nmk) time, O(k) space.
Watch out. Sources spread simultaneously; do not add their distances.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: An infection needs at least Manhattan distance to reach a cell, and a shortest grid path
// achieves that time. The first arriving infection determines each cell’s time.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<cstdlib>
#include<iterator>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<pair<int,int>>a(k);
for(auto&[x,y]:a){
cin>>x>>y;
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int best=INT_MAX;
for(auto[x,y]:a){
best=min(best,abs(i-x)+abs(j-y));
}
ans=max(ans,best);
}
}
cout<<ans<<'\n';
}