Flood Fill Recursive algorithm

Question

Hello I made use of flood fill recursive algorithm to find the connected cells to each other in an 2D array (Here I am using vectors). But this fails for one boundary test case

#include<iostream>
#include<vector>
using namespace std;
int count = 0;
int max_count = 0;
int min_count = 0;

void floodFillUtil(vector< vector<int> > &a,int i,int j,int m,int n,int prevP,int newN)
{
 if (i<0 || i>= m || j<0 || j>=n)
    return;

 if(a[i][j] != prevP)
    return;

count++;
a[i][j] = newN;
floodFillUtil(a,i+1,j+1,m,n,prevP,newN);
floodFillUtil(a,i-1,j-1,m,n,prevP,newN);
floodFillUtil(a,i-1,j+1,m,n,prevP,newN);
floodFillUtil(a,i+1,j-1,m,n,prevP,newN);
floodFillUtil(a,i+1,j,m,n,prevP,newN);
floodFillUtil(a,i,j+1,m,n,prevP,newN);
floodFillUtil(a,i-1,j,m,n,prevP,newN);
floodFillUtil(a,i,j-1,m,n,prevP,newN);

}

void floodFill(vector< vector<int> > &a,int i,int j,int newN,int m,int n)  {
  int prevP = a[i][j];
  floodFillUtil(a,i,j,m,n,prevP,newN);
 }
 // Driver program to test above function
 int main()
{   int m,n;
    cin>>m>>n;
    vector<vector<int> > a;
    vector<int> b;
    for(int i=0;i<m;i++)
    {for(int j=0;j<n;j++)
      {   int temp;
          cin>>temp;
          b.push_back(temp);  
      }
     a.push_back(b);
     b.clear();
    }
  for(int i=0;i<m;i++)
   for(int j=0;j<n;j++) {
    if (a[i][j] == 1){
       floodFill(a,i,j,2+i,m,m);
       min_count = count ;
       if(min_count > max_count){
         max_count = min_count;
       }
    count=0;
    }
}  
for(int i=0;i<m;i++)
{for(int j=0;j<n;j++)
    cout<<a[i][j]<<" ";
    cout<<endl;}
cout<<max_count;

}

And this is the input test case for which it is failing

8
9
0 1 0 0 0 0 1 1 0
1 1 0 0 1 0 0 0 1
0 0 0 0 1 0 1 0 0
0 1 1 1 0 1 0 1 1
0 1 1 1 0 0 1 1 0
0 1 0 1 1 0 1 1 0
0 1 0 0 1 1 0 1 1
1 0 1 1 1 1 0 0 0

And this is output given by code

0 2 0 0 0 0 2 2 0 
2 2 0 0 3 0 0 0 1 
0 0 0 0 3 0 3 0 0 
0 3 3 3 0 3 0 3 1 
0 3 3 3 0 0 3 3 0 
0 3 0 3 3 0 3 3 0 
0 3 0 0 3 3 0 3 1 
3 0 3 3 3 3 0 0 0 
27

But the output should be 29, for [1,8] [3,8] and [6,8] it is not changing.What must be the problem in the code.

How about [1,8] isn't that wrong also? – danh Aug 04 '15 at 19:21 — danh, Aug 04 '15 at 19:21
@danh yes that too, question updated – Suraj Palwe Aug 04 '15 at 19:23 — Suraj Palwe, Aug 04 '15 at 19:23

score 2 · Accepted Answer · edited May 23 '17 at 11:43

2

Looks like a typo here:

floodFill(a,i,j,2+i,m,m);

Should be:

floodFill(a,i,j,2+i,m,n);

Unless your matrix is square. It might be worthwhile to abstract the matrix into an object that knows its own dimensions (see here). Then you can pass fewer parameters everywhere.

edited May 23 '17 at 11:43

Community

1
1

answered Aug 04 '15 at 19:24

danh

62,181
10
95
136

Flood Fill Recursive algorithm

1 Answers1