"Shadow" in C Flood Fill Program

Question

So I'm having some problems with my Flood fill program, basically what happens is that if you enter a shape smaller that the perimeter it comes back with a "shadow" under it, just more rows. For example my code is set up for a size of ten, and if you enter a 8x8, everything under it will be filled too. I'm not really sure where or why the array is getting set to true, but you can see that it is. Here's my code:

// Fill.c
// Takes an input and a x and y that is in side the shape

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

#define size 10 // Change this to change the size of the Grid

bool Grid[size][size];
void fill(int x, int y, bool Grid[size][size]);

main()
{
    int i, u;
    char in[size];

    for(i = 0; i < size; i++)
    {
        for(u = 0; u < size; u++)
        {
            Grid[i][u] = FALSE;
        }
    }

    printf("This program will take in a set of '*' and ' '(Asterisks and spaces) then fill the shape.\nThe shape must be closed.\nThe Grid that you will be using is %dx%d\nPlease enter your text:\n", size, size);

    for(i = 0; i < size; i++)
    {
        gets(in);
        for(u = 0; u < size; u++)
        {
            if(in[u] == '*') Grid[i][u] = TRUE;
            else Grid[i][u] = FALSE;
        }
    }

    printf("Please enter the x(or up and down) coordinate inside the shape:\n");
    int x = GetInteger();
    printf("Please enter the y(or left and right) coordinate inside the shape:\n");
    int y = GetInteger();
    if(Grid[9][5] == TRUE) printf("\nBottom line set to TRUE\n"); // This is a trouble shooting line
    fill(x, y, Grid);


    for(i = 0; i < size; i++)
    {
        for(u = 0; u < size; u++)
        {
            if(Grid[i][u] == TRUE) printf("*");
            else printf(" ");
        }
        printf("\n");
    }

}

void fill(int x, int y, bool Grid[size][size])
{
    int i, u;


    for(i = 0; i < size; i++) // I have this in here as another trouble shooting thing
    {
        for(u = 0; u < size; u++)
        {
            if(Grid[i][u] == TRUE) printf("*");
            else printf(" ");
        }
        printf("\n");
    }
    printf("\n");

    Grid[x][y] = TRUE;
    if(Grid[x][y+1] != TRUE) fill(x, y+1, Grid);
    if(Grid[x][y-1] != TRUE) fill(x, y-1, Grid);
    if(Grid[x+1][y] != TRUE) fill(x+1, y, Grid);
    if(Grid[x-1][y] != TRUE) fill(x-1, y, Grid);
    return;
}

Input (size = 10): Shape input:

 ********
 *      *
 *      *
 *      *
 *      *
 *      *
 *      *
 ********

Coordinates input:

x = 5
y = 5

Output:

 ********
 ********
 ********
 ********
 ********
 ********
 ********
 ********
 ********

Answer 1

There are numerous problems.

• You use gets(), but gets() is too dangerous to be used ever.
• You try to read a line of 10 characters plus a terminal null into an array of 10 characters. This is a buffer overflow.
• You do not check that the read operations worked.
• You do not check that there were 10 characters read.
• You do not use a function to print the grid.

Those are 'simply' I/O handling errors and array boundary check problems.

In the fill() function, you do not ensure that you'll not be probing outside the grid — you don't check that the values such as x-1 or y+1 are within bounds. Granted, if the data is valid, there won't be a problem, but users are horribly unreliable and your program shouldn't crash or invoke undefined behaviour even if the user screws up.

I believe your extra 'shadow' line comes from not paying attention to when the input line terminates. If the last line consists of just a newline, you quietly go reading beyond the end of what was read, and what was in the previous line is copied into the last line. If the last line consists of blanks, you do not run into that problem.

So, all your issues boil down to 'not being careful enough in I/O handling'.

Putting the changes together, and providing a minimal GetInteger() implementation, yields:

/* SO 4245-7124 Shadow in flood-fill program */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

enum { size  = 10 };

bool Grid[size][size];

void fill(int x, int y, bool Grid[size][size]);

static int GetInteger(void)
{
    int n;
    if (scanf("%d", &n) != 1)
    {
        printf("Oops! Did not get an integer.\n");
        exit(EXIT_FAILURE);
    }
    return n;
}

static inline void dash_line(int width)
{
    for (int i = 0; i < width; i++)
        putchar('-');
    putchar('\n');
}

static void print_grid(const char *tag)
{
    printf("Grid %s:\n", tag);
    dash_line(size);
    for (int i = 0; i < size; i++)
    {
        for (int u = 0; u < size; u++)
        {
            if (Grid[i][u] == true)
                printf("*");
            else
                printf(" ");
        }
        printf("\n");
    }
    dash_line(size);
}

int main(void)
{
    int i, u;
    char in[1024];

    for (i = 0; i < size; i++)
    {
        for (u = 0; u < size; u++)
        {
            Grid[i][u] = false;
        }
    }
    print_grid("A");

    printf("This program will take in a set of '*' and ' '\n"
           "(asterisks and spaces) then fill the shape.  The\n"
           "shape must be closed.  The Grid that you will be\n"
           "using is %dx%d. Please enter your text:\n", size, size);

    for (i = 0; i < size; i++)
    {
        if (fgets(in, sizeof(in), stdin) != 0)
        {
            for (u = 0; u < size; u++)
            {
                if (in[u] == '*')
                    Grid[i][u] = true;
                else if (in[u] == '\0')
                    break;
                else
                {
                    /* Treat a newline or anything else as a non-asterisk */
                    /* NB: not strictly necessary because of initializer loops */
                    Grid[i][u] = false;
                }
            }
        }
    }

    print_grid("B");

    printf("Please enter the x (or up and down) coordinate inside the shape:\n");
    int x = GetInteger();
    printf("Please enter the y (or left and right) coordinate inside the shape:\n");
    int y = GetInteger();
    if (Grid[9][5] == true)
        printf("\nBottom line set to true\n");

    fill(x, y, Grid);
    print_grid("C");
}

void fill(int x, int y, bool Grid[size][size])
{
    assert(x >= 0 && x < size && y >= 0 && y < size);

    //print_grid("-->> fill()");

    Grid[x][y] = true;
    if (y + 1 < size && Grid[x][y + 1] != true)
        fill(x, y + 1, Grid);
    if (y - 1 < size && Grid[x][y - 1] != true)
        fill(x, y - 1, Grid);
    if (x + 1 < size && Grid[x + 1][y] != true)
        fill(x + 1, y, Grid);
    if (x - 1 < size && Grid[x - 1][y] != true)
        fill(x - 1, y, Grid);

    //print_grid("<<-- fill()");
}

Note that the code does not validate that each coordinate of the entered starting position falls within the range 0..size-1 (but it should — the assertion will fire if you get it wrong, though, but an assertion is a bad way of validating user input). It does allow for vastly long lines (up to 1 KiB) and ignores the excess data on a long line. It handles short lines sanely, treating the missing data as all blank.

You can reinstate the printing within fill() if you choose. With a little care, you could make that a command line option. If you made the data reading loops into a function, you could arrange to read from a file specified on the command line. Such tweaks are probably beyond the range of what you want to do for this class exercise.

My test data was variants on the file:

  **  **  
** *  * *
*   **   *
*        *
 *       *
  *     * 
   *   *  
   *   *  
   *****  

4 4

Leaving off the last row of asterisks is a mildly interesting exercise.