Islands in a Photograph
National Olympiad — Municipal round (2010 season)
Submission name: pic.cpp
Problem summary
A binary photograph uses 1 for land and 0 for water. Land pixels are connected even across a corner. Count land components entirely surrounded by water. Everything beyond the photograph is land, so a component touching its border is not an island.
Input
M N followed by M rows of N space-separated binary pixels.
Output
The number of islands.
Constraints
2 < M,N < 100.
Worked example
An independently prepared example for this explanation.
Input
3 3 0 0 0 0 1 0 0 0 0
Output
1
Solution analysis
- Visit each unvisited land pixel and flood fill its component using all eight neighboring directions. The examples with diagonal connections establish that corner-touching land is connected.
- During a fill remember whether any component pixel lies in the first or last row or column. Such a component connects to the exterior land and is excluded. Count a component only when the entire fill finishes without touching the border.
- The sample has a single central land pixel with water around it and no border contact, so its component contributes one island. In the official second example the diagonal pixel joins the larger land component.
Why it works
Eight-neighbor flood fill reaches exactly the pixels connected to its starting pixel, and marking on insertion visits each once. A component meets exterior land exactly when it contains a border pixel. Therefore counting exactly the filled components without such a pixel gives all and only the islands.
Watch out. Use eight directions. A component touching the border at just one corner still belongs to exterior land.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
int main(){
// Compute the exact archive answer using the method explained above.
int rows,columns;
cin>>rows>>columns;
vector<vector<int>>land(rows,vector<int>(columns));
for(auto&row:land){
for(int&pixel:row){
cin>>pixel;
}
}
int answer=0;
for(int r=0;r<rows;r++){
for(int c=0;c<columns;c++){
if(land[r][c]==0){
continue;
}
queue<pair<int,int>>pending;
pending.push({r,c});
land[r][c]=0;
bool border=false;
while(!pending.empty()){
auto[x,y]=pending.front();
pending.pop();
border=border||x==0||y==0||x==rows-1||y==columns-1;
for(int dx=-1;dx<=1;dx++){
for(int dy=-1;dy<=1;dy++){
int nx=x+dx;
int ny=y+dy;
if(nx>=0&&nx<rows&&ny>=0&&ny<columns&&land[nx][ny]){
land[nx][ny]=0;
pending.push({nx,ny});
}
}
}
}
answer+=!border;
}
}
cout<<answer<<'\n';
}