Iterative Flood Fill implementation in C [closed]

I am trying to implement an iterative version of flood fill in C:

#include<stdio.h>
int m,n;
void flood_fill(int [][n],int,int,int);
void print_wall(int [][n]);
int main(void)
{
int i,j;
scanf("%d%d",&m,&n);
int arr[m][n];
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&arr[i][j]);
}
}
int x,y;
printf("Enter the coordinates of the point to be repainted\n");
scanf("%d%d",&x,&y);
int new_col;
printf("Enter new color to be painted");
scanf("%d",&new_col);
flood_fill(arr,x,y,new_col);
print_wall(arr);
return 0;
}

void flood_fill(int a[][n],int x,int y,int n)
{
int i,j;
for(i=x+1;i<m-1;i++)
{
for(j=y;j<n-1;j++)
{

if(a[i][j]==a[x][y])
a[i][j]=n;

}
}
for(i=x;i>0;i--)
{
for(j=y-1;j>0;j--)
{

if(a[i][j]==a[x][y])
a[i][j]=n;

}
}
for(i=x+1;i<m-1;i++)
{
for(j=y;j>0;j--)
{

if(a[i][j]==a[x][y])
a[i][j]=n;

}
}
for(i=x;i>0;i--)
{
for(j=y+1;j<n-1;j++)
{
if(a[i][j]==a[x][y])
a[i][j]=n;

}
}
a[x][y]=n;
}

void print_wall(int a[][n])
{
int i,j;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf("%d",a[i][j]);
}
printf("\n");
}

}


Is my implementation correct? Is the stack/queue implementation better?

• main() seems to lack one level of indentation... – glampert Sep 2 '14 at 1:13
• Asking for a correctness of the code which is obviously incorrect (it fails to fill up any non-convex area - in fact, it only fills rectangles)?.. Besides, revisit use of parameter n. Voting to close. – vnp Sep 2 '14 at 5:39
• Correctness for corner cases is on-topic. – Pimgd Sep 2 '14 at 7:38

1. There is no need to have m and n as global variables. Create a structure to hold your data members together and pass a pointer to that structure to your functions.

2. Variable names are too short and not intuitive: m, n, arr, i, j, x, y etc. Use better names (ex: numberOfRows, numberOfCols etc) that explain what the variable is doing.

3. For readability reasons I would go with a recursive implementation. My second choice would be a stack based, if recursivity is not an option. And if performance would really be an important point of my implementation that I would do something similar but:

• I would create a struct MatrixMap that would hold my matrix, number_of_rows and number_of_cols.

• I would represent the position of an element from the MatrixMap using a structure MatrixMapCoordinate having two size_t values, Row and Column.

• An element from the MatrixMap can be represented using a structure MatrixMapElement.

• Accessing an element can be done with a function similar with:

const MatrixMapElement* ElementAt(const MatrixMap* fromMap, const MatrixMapCoordinate* atPosition);

• I would move in my matrix using specialized functions such as MoveWest, MoveNorth, MoveEast and MoveSouth. You can even send flags to control the movement behavior: SkipAllEmptyCells, MoveOneCell etc.

Lastly, what I said at point 2 and 3 I would rewrite my algorithm as close as possible to the actual pseudocode.

//Read "elements" as color in the algorithm.
//  I decided to use element instead of color so you can use it in any kind of problem, regardless of what does your matrix contains.
void FloodFill(MatrixMap* targetMap, const MatrixMapCoordinate* startingCoordinate, const MatrixMapElement* targetElement, const MatrixMapElement* replacementElement)
{
//If the starting coordinate is out of range we end the fill
if (HasElementAt(targetMap, startingCoordinate))
return;

//Check if the element at the startingCoordinate is of the targetElements.
if (ElementsAreEqual(ElementAt(targetMap, startingCoordinate), targetElement))
return;

//If both target and replacement are equal there is nothing to do.
if (ElementsAreEqual(targetElement, replacementElement))
return;

SetElementValue(targetMap, startingCoordinate, replacementElement);

FloodFill(targetMap, MoveWest(startingCoordinate), targetElement, replacementElement);
FloodFill(targetMap, MoveNorth(startingCoordinate), targetElement, replacementElement);
FloodFill(targetMap, MoveSouth(startingCoordinate), targetElement, replacementElement);
FloodFill(targetMap, MoveEast(startingCoordinate), targetElement, replacementElement);
}


Note that there is no error or pointer check. I wrote the code just to give you an idea on how it should look from a readability point of view.

You can do a similar implementation for any algorithm you choose.

Because of the poor readability in your initial implementation I didn't spend time to validate your logic. Though I would be more than happy to do it, if you refactor your code using some of the suggestions I gave you.