3
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ main() seems to lack one level of indentation... \$\endgroup\$ – glampert Sep 2 '14 at 1:13
  • \$\begingroup\$ 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. \$\endgroup\$ – vnp Sep 2 '14 at 5:39
  • 1
    \$\begingroup\$ Correctness for corner cases is on-topic. \$\endgroup\$ – Pimgd Sep 2 '14 at 7:38
3
\$\begingroup\$
  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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.