Ivo -4 years ago 128
C Question

# FloodFill Function call not working

I had to use for the first time flood fill algorithm in order to solve a task from a homework. The main problem is that it seems that the call of the flood fill function I wrote doesn`t work.

My task is something very similar to the one described here:
How can I find hole in a 2D matrix?

I used an algorithm from here: http://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm and I adapted it to what I need.

I have for example this matrix:

``````0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 1 1 0 1 0
0 1 1 1 1 1 0 0 1 0
0 0 1 1 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
``````

And I want to transform it in something like this:

``````0 0 0 0 0 0 0 0 0 0
0 0 0 2 2 0 0 0 0 0
0 0 2 2 2 2 2 0 3 0
0 2 2 2 2 2 0 0 3 0
0 0 2 2 2 0 0 0 3 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 4 4 4 4 4 4 0 0 0
0 0 0 4 4 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
``````

and also to count the elements of every "area" or cluster.

In the main program, I search for the first element equal to 1 and send his position (x,y) to the function "color" (flood fill function) to become the "seed".

I tried to find the bugs using gdb - found nothing.
I added some printf() to the code to see what is happening - everything works fine until I call the function "color" and then nothing happens.
I searched the internet for a solution but I didn`t find something to solve this.

Here is the code of the flood-fill:

``````int color(int x,int y,int n,int**sim,int nr, int h, int w)
{
if (x < h && y < w)
if( sim[x][y] == 1 )
{
sim[x][y] = n;
printf ("%d %d   ", x, y);//it does not print anything here

if (sim[x-1][y] != 1 && sim[x+1][y] != 1 && sim[x][y-1] != 1 && sim[x][y+1] != 1)
return nr; /*this happens when everything around is equal to 0 or n, so there is nothing to modify and the program should end*/
else
{
nr++;
color(x-1,y,n,sim,nr,h,w);
color(x+1,y,n,sim,nr,h,w);
color(x,y-1,n,sim,nr,h,w);
color(x,y+1,n,sim,nr,h,w);
}
}
}
``````

And the call in the main function:

``````int **s;
s = malloc(m*sizeof(int *));
for(i=1; i <= h; i++)
s[i] = malloc(m*sizeof(int));
a=0;
b=0;
while (a <= h && b <= w)
{
k = 0;
for(i=a; i < h && k == 0; i++)
for(j=b; j < w; j++)
if( s[i][j] == 1 ) //find the first element = 1 and stop to its position
{k = 1; printf("%d %d ", i, j);}
printf("\n");
if(k == 1)
{
a = i;
b = j;
nr = color(i,j,c,s,0,h,w); //call the function
printf("%d,%d,%d,%d ", k, c, i, j);
cluster[c] = nr;
c++;
}
if (k == 0)
break; //if it is no area left to modify
}
``````

I am a beginner and I have never used flood fill before. I am not even sure what is wrong: the flood fill code, the call of the function, or the way I pass the matrix sim[][] in the function. What is wrong?

There are numerous errors in the OP code, for example using the H and V array directions interchanged, and not checking the array bounds to prevent the recursion travelling off the edge of the array to continue wherever it happens to find a '1', or worse, accessing memory with an undefined pointer.

``````#include <stdio.h>
#include <stdlib.h>

#define h  11   // height
#define w  10   // width

void color(int x, int y, int n, int **sim, int *nr) {
if (x>=0 && x<w && y>=0 && y<h && n>1) {
if( sim[y][x] == 1 ) {
sim[y][x] = n;
(*nr)++;
color(x-1, y,   n, sim, nr);
color(x+1, y,   n, sim, nr);
color(x,   y-1, n, sim, nr);
color(x,   y+1, n, sim, nr);
}
}
}

void show(int **sim) {
int i, j;
for (j=0; j<h; j++) {
for (i=0; i<w; i++) {
printf ("%3d", sim[j][i]);
}
printf ("\n");
}
printf ("\n");
}

int main() {
int **s;
int n, i, j, nr;
s = malloc(h*sizeof(int *));
for(j=0; j<h; j++)
s[j] = malloc(w*sizeof(int));
for (j=0; j<h; j++)
for (i=0; i<w; i++)
s[j][i] = rand() % 2;
show(s);

n = 2;
for (j=0; j<h; j++) {
for (i=0; i<w; i++) {
if (s[j][i] == 1) {
nr = 0;
color(i, j, n, s, &nr);
printf("%3d,%3d,%3d,%3d\n", i, j, n, nr);
n++;
}
}
}
printf ("\n");
show(s);

for(i=h-1; i>=0; i--)
free (s[i]);
free (s);
return 0;
}
``````

Program output.

``````1  1  0  0  1  0  0  0  0  0
1  1  1  1  1  1  1  0  1  0
1  0  0  1  0  0  1  0  0  1
1  0  1  0  1  0  1  1  1  0
1  1  0  1  1  0  1  1  1  0
1  0  0  1  1  1  1  1  1  0
0  1  0  0  0  0  0  0  0  0
0  1  0  1  0  0  0  1  1  0
1  1  0  0  0  0  0  0  1  0
0  1  0  1  1  0  0  0  1  1
1  1  1  0  0  0  1  0  1  0

0,  0,  2, 32
8,  1,  3,  1
9,  2,  4,  1
2,  3,  5,  1
1,  6,  6,  8
3,  7,  7,  1
7,  7,  8,  6
3,  9,  9,  2
6, 10, 10,  1

2  2  0  0  2  0  0  0  0  0
2  2  2  2  2  2  2  0  3  0
2  0  0  2  0  0  2  0  0  4
2  0  5  0  2  0  2  2  2  0
2  2  0  2  2  0  2  2  2  0
2  0  0  2  2  2  2  2  2  0
0  6  0  0  0  0  0  0  0  0
0  6  0  7  0  0  0  8  8  0
6  6  0  0  0  0  0  0  8  0
0  6  0  9  9  0  0  0  8  8
6  6  6  0  0  0 10  0  8  0
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download