Spoj Herding – Flood fill algorithm

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/


    

      

        

  

    
    


        


  


  

        

          

          
#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;
        
        

          

          
}
        
        

          

          


        
  



    

  


      
      

        view raw
        
          herdings.cpp
        
        hosted with ❤ by GitHub