I recently came across an interesting algorithm called flood fill algorithm.It is used in computer graphics to fill connected same colored pixels with
a replacement color.
The algorithm goes like this
Flood-fill (node, target-color, replacement-color): 1. If the color of node is not equal to target-color, return. 2. Set the color of node to replacement-color. 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color). Perform Flood-fill (one step to the east of node, target-color, replacement-color). Perform Flood-fill (one step to the north of node, target-color, replacement-color). Perform Flood-fill (one step to the south of node, target-color, replacement-color). 4. Return. using this algorithm lets solve a spoj problem-HERDING http://www.spoj.com/problems/HERDING/This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
#include<iostream> using namespace std; char grid[1000][1000]; int flag[1000][1001]={0},r,c; int count=0,prev_count=0; void floodfill(int i,int j){ if(i>=0&&j>=0&&i<r&&j<c) if(flag[i][j]==0){ flag[i][j]=count; switch(grid[i][j]){ case 'E':floodfill(i,j+1); break; case 'W':floodfill(i,j-1); break; case 'N':floodfill(i-1,j); break; case 'S':floodfill(i+1,j); break; } flag[i][j]=count; } else{ count=flag[i][j]; return; } } int main(){ cin>>r>>c; for(int i=0;i<r;i++) cin>>grid[i]; for(int i=0;i<r;i++){ for(int j=0;j<c;j++){ if(flag[i][j]==0){ count=prev_count+1; floodfill(i,j); if(prev_count<count) prev_count++; } } } cout<<prev_count<<endl; }