Virus Seeds
National Olympiad — Regional round
Submission name: viruses.cpp
Problem summary
In an n by m grid, infection spreads between orthogonally adjacent unprotected cells. Protected cells cannot be infected or crossed. Find the fewest initially infected cells needed eventually to infect every unprotected cell.
Input
n m; k followed by k pairs of 1-based protected-cell coordinates.
Output
The minimum number of initial infections.
Constraints
1 ≤ n,m ≤ 100; 0 ≤ k ≤ nm; valid row and column coordinates.
Worked example
An independently prepared example for this explanation.
Input
2 3 2 1 2 2 2
Output
2
Solution analysis
- Treat every unprotected cell as a vertex and count connected components by iterative DFS.
- One seed reaches its entire component, but cannot leave it.
Why it works
Every nonempty component needs a seed and one seed is sufficient. Therefore the component count is both necessary and attainable.
Watch out. An entirely protected grid needs zero seeds. Diagonal contact does not spread infection.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every nonempty component needs a seed and one seed is sufficient. Therefore the component
// count is both necessary and attainable.
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>>a(n,vector<int>(m));
while(k--){
int x,y;
cin>>x>>y;
a[x-1][y-1]=1;
}
int ans=0,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(!a[i][j]){
ans++;
vector<pair<int,int>>s={{i,j}};
a[i][j]=1;
while(!s.empty()){
auto[x,y]=s.back();
s.pop_back();
for(int d=0;d<4;d++){
int u=x+dx[d],v=y+dy[d];
if(u>=0&&u<n&&v>=0&&v<m&&!a[u][v]){
a[u][v]=1;
s.push_back({u,v});
}
}
}
}
}
}
cout<<ans<<'\n';
}