this is similar to the Pixel fill algorithm usually used in photo editing softwares (photoshop or paint )
BFS would be best approach to start with ( and check 4-adjacent or 8-includeing diagonal elements for a '1' and include that to queue. When the queue becomes empty, increase the count by 1. repeat until all the elements are processed and return "count" http://ideone.com/OUYpd NOTE: This is a similar code, but logic is a same, certain terminology is different, and the example discussed above will have only 1 island according to the below code. If two islands is expected (diagonals not considered, 4 condition in the while have to be removed) #include<stdio.h>#include <queue>#include <stdlib.h> using namespace std; struct POS{ int row_no; int col_no;}; queue<POS> Q; POS get_POS(int row,int col){ POS p; p.row_no = row; p.col_no = col; return p;} void FILL_PIXELS(char filename[10]){ FILE *p = fopen(filename,"r"); if(p==NULL) exit(1); //while() int rows=0,cols=0; fscanf(p,"%d %d\n",&rows,&cols); char array[rows][cols+1]; //fflush(stdin); int i=0; for(;i<rows-1;i++){ fgets(array[i],cols+2,p);//fgets(array[i],cols,stdin); //printf("%3d %s",i,array[i]); } fgets(array[i],cols+1,p); //printf("%s\n",array[i]); //char queue[rows*cols]; fclose(p); int no_of_fills=0; for(int i=0;i<rows;i++){ //printf("%d\n",i); for(int j=0;j<cols;j++){ if(array[i][j] == '0'){ no_of_fills++; POS p; p.row_no = i; p.col_no = j; //array[i][j] = '1'; Q.push(p); array[i][j] = '1'; while(!Q.empty()){ POS p = Q.front(); Q.pop(); int x = p.row_no; int y = p.col_no; //array[x][y] = '1'; //printf("%3d,%3d\n",x,y); if(x>0 && y>0 && array[x-1][y-1] == '0'){ Q.push(get_POS(x-1,y-1)); array[x-1][y-1] = '1'; } if(x>0 && array[x-1][y]=='0'){ Q.push(get_POS(x-1,y)); array[x-1][y] = '1'; } if(x>0 && y<(cols-1) && array[x-1][y+1]=='0'){ Q.push(get_POS(x-1,y+1)); array[x-1][y+1] = '1'; } if(y>0 && array[x][y-1]=='0'){ Q.push(get_POS(x,y-1)); array[x][y-1] = '1'; } if(y<(cols-1) && array[x][y+1]=='0'){ Q.push(get_POS(x,y+1)); array[x][y+1] = '1'; } if(y>0 && x<(rows-1) && array[x+1][y-1]=='0'){ Q.push(get_POS(x+1,y-1)); array[x+1][y-1] = '1'; } if(x<(rows-1) && array[x+1][y]=='0'){ Q.push(get_POS(x+1,y)); array[x+1][y] = '1'; } if(x<(rows-1) && y<(cols-1) && array[x+1][y+1]=='0'){ Q.push(get_POS(x+1,y+1)); array[x+1][y+1] = '1'; } } } } } /*p = fopen("a.out","w"); fprintf(p,"%d",no_of_fills); fclose(p);*/ printf("%d\n",no_of_fills);} int main(int argc,char **argv){ FILL_PIXELS(argv[1]);} -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/YTHGgaxrPy0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
