Advanced Recursion - Flood Fill

Section 21.10 Advanced Recursion - Flood Fill

Recursion often excels for problems that can be solved using a divide and conquer strategy. Divide and conquer means breaking a problem down into smaller, similar sub-problems, solving those sub-problems, and then combining the results to solve the original problem. (Even description of the strategy should sound a lot like how we have described recursion.)

🔗

A classic example of this is the flood fill algorithm, which is used in computer graphics to fill an area with a color. We will look at a simple version of flood fill that “colors” in elements of a 2D matrix. Flood fill starts from a single point and keeps spreading out, only stopping when we reach the edge of the area or a different color.

🔗

    ###
    # #
##### #
# .   #
#  ####
####

Figure 21.10.1. Flood Fill Start. We begin filling the area at the .

🔗

    ###
    #.#
#####.#
#.....#
#..####
####

Figure 21.10.2. Flood Fill End. All the blank areas inside the region are filled with ..

🔗

Let us consider the recursive design questions. As we do so, let us stop and think about what one “worker” should be responsible for doing. What is the tiniest version of “fill in this area with paint”? It seems like the smallest area we can consider is a single cell. So that will be the work we focus on in each recursive call.

What are the inputs/outputs 🔗: Input: a 2D matrix and a starting point; Output: nothing, we will just modify the matrix.
🔗
What is the base case 🔗: We have reached a cell that is not blank, or we have gone outside the bounds of the matrix. So there are two base cases. In both, there is nothing to do, we just need to return.
🔗
What is the recursive case 🔗: We will fill in the current cell with the new color, and then recursively call floodFill on the four neighboring cells (up, down, left, right).
🔗

🔗

It almost seems like cheating. How do you flood fill? You fill one square and then ask the neighbors to flood fill.

🔗

Checkpoint 21.10.1.

Build the flood fill algorithm. Tip: we need to test the “out of bounds” test case BEFORE we try to check if the current location is already filled in.

🔗

void floodFill(vector<vector<char>>& picture, 
                 size_t curRow, size_t curCol) {
---
    size_t rows = picture.size();
    size_t cols = picture.at(0).size();
---
    if (curRow >= rows || curCol >= cols) {
---
        return; // went out of bounds - done
    }
---
    if (picture.at(curRow).at(curCol) != ' ') {
---
        return; // hit a filled square - done
    }
---
    // mark the current square
    picture.at(curRow).at(curCol) = '.';
    printMaze(picture); // show what it looks like now
---
    floodFill(picture, curRow, curCol - 1); // left
    floodFill(picture, curRow, curCol + 1); // right
    floodFill(picture, curRow - 1, curCol); // up
    floodFill(picture, curRow + 1, curCol); // down
---
}

🔗

Once you build the algorithm, make sure to run it. Then scroll through the output. Because we print at each step of the algorithm, you can see the process play out. To see even more information about what is going on, add `cout << "Checking" << curRow << ", " << curCol << endl; as the first line inside floodFill`. You will get to see evidence of all of the function calls, even those that are a base case and do not do anything.

🔗

Note 21.10.1.

We are not checking if curRow or curCol are less than 0 because they are of type size_t. A size_t can not be negative. If it is 0, and you subtract 1 from it, it will wrap around to the largest possible number it can represent. (Similar to the large value string::npos represents.)

🔗

So curRow >= rows will catch both “The row number got too big” and “we went below 0”. If there are 10 rows and we go to row 11, that is out of bounds. If we are at row 0 and try to subtract 1, we will end up with a value like 18446744073709551615. That will also count as out of bounds.

🔗

You can test this by changing main so the start row is 0 and the start col is 4. That location is not surrounded by walls.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next