uva 10946 (You want what filled?)


Algorithm used : Flood Fill

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define MAX 100
char graph[MAX][MAX];
int countER;
int floodFill(int r, int c, char target);
int row,col;

int main(){
    freopen("inMe.txt","r",stdin);
    freopen("outMe.txt","w",stdout);
    
    int testCase = 1;
    
    
    while(scanf("%d %d",&row,&col)==2 && !(row==0&&col==0)){   
     for(int i=0;i<row;i++)scanf("%s",&graph[i]);
     
     int charArray[5000];
     int freq[5000];
     int start = 0;
     for(int i=0;i<row;i++){
       for(int j=0;j<col;j++){
        if(graph[i][j]>='A'&&graph[i][j]<='Z'){
         countER = 0;
         
         charArray[start] = (int)graph[i][j];
         freq[start] = floodFill(i,j,graph[i][j]); 
         if(freq[start]==0)freq[start]=1;
         start++; 
        }
       }
     }
    
   
    
    for(int a=1;a<start;++a){
     for(int b=start-1;b>=a;--b){
      if(freq[b-1]<freq[b] || (freq[b-1]==freq[b]&&charArray[b-1]>charArray[b]) ){
         int temp=freq[b-1];
       freq[b-1]=freq[b];
       freq[b]=temp;
       
        temp=charArray[b-1];
        charArray[b-1]=charArray[b];
        charArray[b]=temp;
       
      }

     }
     }
     printf("Problem %d:\n",testCase++);
     for(int i=0;i<start;i++){
      printf("%c %d\n",charArray[i],freq[i]);
    }
    
    }
    return 0;
}

int floodFill(int r, int c, char target){
    int temp1,temp2;
    temp1=r;
    temp2=c+1;
    if(temp2<col&&(graph[temp1][temp2]==target)){
        countER++;
        graph[temp1][temp2]='.';
       floodFill(temp1,temp2,target);
    }
    temp1=r;
    temp2=c-1;
    if(temp2>=0&&graph[temp1][temp2]==target){
        countER++;
        graph[temp1][temp2]='.';
        floodFill(temp1,temp2,target);
    }
    temp1=r-1;
    temp2=c;
    if(temp1>=0&&graph[temp1][temp2]==target){
        countER++;
        graph[temp1][temp2]='.';
        floodFill(temp1,temp2,target);
    }
    temp1=r+1;
    temp2=c;
    if(temp1<row&&graph[temp1][temp2]==target){
        countER++;
        graph[temp1][temp2]='.';
        floodFill(temp1,temp2,target);
    }
    
   return countER; 

}

About these ads

Tagged: , , , ,

Did it help you ....?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: