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
*****
*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!
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);