I have an assignment where I need to write a recursive flood fill algorithm to fill in spaces in ASCII art with incrementing characters. Now, I have done endless research and think I understand the basic fundamentals of this algorithm. However, when I apply what I learned, the output does not produce what I want. The following is the outline of the program

1. Find the 'A' within the room where an '*' represents a wall. You can assume there will always be an 'A'.
2. Start at A and fill the room with incrementing characters up until Z and keep going with Z if Z is reached. Example output:

*****
*DCB*
***A*
*DCB*
*****

Below is a sample program as the original is much bigger.

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

typedef struct room{

    char **array;
    int rows;
    int cols;

} room;

void printRoom(room room);
int *findA(room room);
void floodFill(room room, int x, int y, char paint);

int main(int argc, char *argv[]){

    // Make a new room
    room newRoom;

    // Set the rows and columns
    newRoom.rows = 5;
    newRoom.cols = 5;

    // Allocate memory for the array
    newRoom.array = malloc(newRoom.rows * sizeof(char*));
    for(int i = 0; i < newRoom.rows; i  ){
        newRoom.array[i] = malloc(newRoom.cols * sizeof(char));
    }

    // Fill the first array with "*****"
    for(int i = 0; i < newRoom.cols; i  ){
        newRoom.array[0][i] = '*';
    }

    // Fill the second array with "*   *"
    newRoom.array[1][0] = '*';
    newRoom.array[1][1] = ' ';
    newRoom.array[1][2] = ' ';
    newRoom.array[1][3] = ' ';
    newRoom.array[1][4] = '*';

    // Fill the third array with "**A*"
    newRoom.array[2][0] = '*';
    newRoom.array[2][1] = '*';
    newRoom.array[2][2] = '*';
    newRoom.array[2][3] = 'A';
    newRoom.array[2][4] = '*';

    // Fill the fourth array with "*   *"
    newRoom.array[3][0] = '*';
    newRoom.array[3][1] = ' ';
    newRoom.array[3][2] = ' ';
    newRoom.array[3][3] = ' ';
    newRoom.array[3][4] = '*';

    // Fill the fifth array with "*****"
    for(int i = 0; i < newRoom.cols; i  ){
        newRoom.array[4][i] = '*';
    }
    
    printf("Before\n");
    printRoom(newRoom);

    // Find the A
    int *a = findA(newRoom);

    // Print the A
    printf("A is at %d, %d\n", a[0], a[1]);

    // Flood fill the room
    floodFill(newRoom, a[0], a[1], 'A');

    // Print the room
    printf("\nAfter\n");
    printRoom(newRoom);
    

    return 0;
}

int *findA(room room){

    int *location = malloc(2 * sizeof(int));

    for(int i = 0; i < room.rows; i  ){
        for(int j = 0; j < room.cols; j  ){
            if(room.array[i][j] == 'A'){
                location[0] = i;
                location[1] = j;
            }
        }
    }

    return location;
}

void floodFill(room room, int x, int y, char paint){

    // If the current position is a wall, return
    if(room.array[x][y] == '*'){
        return;
    }

    // If the current position is already painted, return
    if(room.array[x][y] == paint){
        return;
    }

    if(x < 0 || x >= room.rows || y < 0 || y >= room.cols){
        return;
    }

    // Paint the current position
    room.array[x][y] = paint;

    // Flood fill the left position
    floodFill(room, x, y   1, paint);

    // Flood fill the right position
    floodFill(room, x, y - 1, paint);

    // Flood fill the top position
    floodFill(room, x   1, y, paint);

    // Flood fill the bottom position
    floodFill(room, x - 1, y, paint);
}

void printRoom(room room){

    for(int i = 0; i < room.rows; i  ){
        for(int j = 0; j < room.cols; j  ){
            printf("%c", room.array[i][j]);
        }
        printf("\n");
    }
}

Output

Before
*****
*   *
***A*
*   *
*****
A is at 2, 3

After
*****
*   *
***A*
*   *
*****

What I think part of the problem is that in the version above, when the first call to floodFill is made, it checks if the current position is equal to paint. In this case it is and then immediately returns and does nothing. However, if I change this line:

From

floodFill(newRoom, a[0], a[1], 'A');

To

floodFill(newRoom, a[1], a[0], 'A');

Output

*****
*   *
***A*
*   *
*****
A is at 2, 3

After
*****
*   *
***A*
*AAA*
*****

As you can see it somewhat filled out the bottom half but not the top. What I think is happening here is that since A is already there when it tries to go up, it exits as the current position is already A when the room was made. Now I'm not sure what to do as I keep getting stuck. If I try to change the base cases I will get infinite recursive calls or it will not do anything at all. In addition, I'm not sure if I need two char parameters in the floodFill function (char oldPaint, char newPaint) to handle the incrementing of characters. Any help is greatly appreciated!

CodePudding user response：

There are these issues:

• The algorithm stops immediately, because it finds that at position x, y the paint character ('A') is already there. To solve this, I would write a wrapper function (floodFillStart) that first replaces that 'A' with a space, and then calls floodFill.

• The check whether the x and y coordinate are out of range, should happen before any access to the matrix. So that if statement should come first.

• The logic to fill with the next character is missing.

• The check room.array[x][y] == paint is not good enough once the character is changing: the algorithm will bump into a character that has the preceding value (where the "flood" came from). This could read room.array[x][y] != ' ', so performing the wall-check at the same time.

void floodFill(room room, int x, int y, char paint){
    // First this
    if(x < 0 || x >= room.rows || y < 0 || y >= room.cols){
        return;
    }

    // If the current position is not a free spot...
    if(room.array[x][y] != ' '){ 
        return;
    }

    room.array[x][y] = paint;

    // Increment the character to paint with
    if (paint < 'Z') {
        paint  ;
    } 

    floodFill(room, x, y   1, paint);
    floodFill(room, x, y - 1, paint);
    floodFill(room, x   1, y, paint);
    floodFill(room, x - 1, y, paint);
}

void floodFillStart(room room, int x, int y){
    // Temporarily clear the starting spot
    if (room.array[x][y] == 'A') {
        room.array[x][y] = ' ';
    } 
    floodFill(room, x, y, 'A');
}

In the main program call:

floodFillStart(room, x, y);

CodePudding user response：

The problem is that, at the start, the initial cell already contains an A character, so the function immediately returns. One approach is to clear the initial cell before calling floodFill the first time from main, as follows:

    // Flood fill the room
    newRoom.array[a[0]][a[1]] = ' ';
    floodFill(newRoom, a[0], a[1], 'A');

This produces the following output:

Before
*****
*   *
***A*
*   *
*****
A is at 2, 3

After
*****
*AAA*
***A*
*AAA*
*****