Count White Grid Components
National Olympiad — Regional round (2016 season)
Submission name: grid.cpp
Problem summary
Labels spread through side-adjacent white cells. Start another label for each unlabelled group and find the largest label used: the white component count.
Input
M N, then M×N values:0 white,1 black.
Output
The number of white connected components.
Constraints
0 < M,N < 200; the first cell is white.
Worked example
Input and output for the worked example discussed below.
Input
2 4 0 1 1 0 0 0 1 1
Output
2
Solution analysis
- A label fills exactly one connected component. Scan every cell; when an unvisited white cell appears, increment the answer and run BFS from it.
- Explore only the four side-neighbours. Mark a white cell when it enters the queue, preventing duplicate entries. Using1 as the visited marker is safe because both black and processed cells must be skipped.
- The sample has a three-cell white group at the left and one isolated top-right cell. Two BFS starts give answer2. Diagonal contact does not connect cells.
Why it works
BFS visits every white cell connected to its start and no others. Marking the whole component prevents another start there. The outer scan therefore starts exactly once in each component.
Watch out. White is0, not1. Mark on enqueue and do not include diagonal moves or use an unsafe deep recursive flood fill.
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(){
int rows;
int columns;
cin>>rows>>columns;
vector<vector<int>>grid(rows,vector<int>(columns));
for(auto&row:grid){
for(int&cell:row){
cin>>cell;
}
}
const int dr[4]={-1,1,0,0};
const int dc[4]={0,0,-1,1};
int components=0;
for(int row=0;row<rows;row++){
for(int column=0;column<columns;column++){
if(grid[row][column]!=0){
continue;
}
components++;
queue<pair<int,int>>pending;
pending.push({row,column});
grid[row][column]=1;
while(!pending.empty()){
auto[r,c]=pending.front();
pending.pop();
for(int direction=0;direction<4;direction++){
int nr=r+dr[direction];
int nc=c+dc[direction];
if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&grid[nr][nc]==0){
// Mark at discovery to enqueue each cell once.
grid[nr][nc]=1;
pending.push({nr,nc});
}
}
}
}
}
cout<<components<<'\n';
}