Competitive/Collaborative Programming Class

Flood Fill

Flood fill is a topic that commonly comes up in discussions about graphic primitives. In this context, flood fill is an algorithm which files the inside of a bounded region with a value (i.e. fill a circle with the color green).

The base flood fill algorithm has many additional uses (some of which will be discussed below). To help visualize flood fill, imagine water being poured on top of a hill (and ignore it being absorbed by the dirt). The water will flow until it reaches the lowest point. The water "floods" the lowest places.

As normal, Wikipedia is a great place to go to learn about a topic (in this case flood fill).

Typically, flood fill processes a 2-D grid (2-D array). Normally it works by looking at the 8 (or 4) cells around a given location (x,y). Flood fill can be implemented both breadth first or depth first. If doing breadth first, the process can be done via two nested loops to process the matrix (slow but simple to code). Breadth first can also be done by storing next tries in a list. Depth first just about has to be implemented using a list of additional places to go to.

Here is a very simple, recursive implementation of depth first. It uses the stack of pending calls to store all of the future places to visit. The process of filling each spot marks it as found. Future visits may then visit this spot, discover it has been filled and then bail out (dynamic programming example - recursive implementation with result caching [marking of filled spots]).

FUNCTION fill(int x, int y)
 BEGIN
    map(x,y) = FULL
    FOR x1,y1=neighborOf(x,y)
       IF (EMPTY == map(x1,y1))
        THEN 
          fill(x1,y1)
        END IF
     END FOR
 END

In this example, neighborOf is a magic function that produces a list of all of the "neighboring" spots (i.e. the four or eight or whatever points that are adjacent to a given point).

Very similar code can implement breadth first (test 4 directions only):

FUNCTION fill(int x, int y)
 BEGIN
    map(x,y) = FULL
    IF (EMPTY == map(x+1, y) 
     THEN 
       fill(x+1, y)
     END IF
    IF (EMPTY == map(x-1, y)
     THEN 
       fill(x-1, y)
     END IF
    IF (EMPTY == map(x, y+1)
     THEN 
       fill(x, y+1)
     END IF
    IF (EMPTY == map(x, y-1)
     THEN 
       fill(x, y-1)
     END IF
 END

Flood fill can be used to solve a maze. If you wanted to know if a maze is solvable (given a starting point, can you reach the ending point?), you do something like this:

FUNCTION fill(int x, int y)
 BEGIN
    map(x,y) = FULL
    FOR x1,y1=neighborOf(x,y)
       IF (EMPTY == map(x1,y1))
        THEN 
          fill(x1,y1)
        END IF
     END FOR
 END
MAIN BEGIN
 fill(startX, startY)
 IF (filled(map(solveX, solveY)))
  THEN 
    PRINT "solvable"
  ELSE 
    PRINT "unsolvable"
  END IF
END MAIN

Pretty cool! But now, I bet you want to know the minimum number of steps to solve the maze. Here is a variant that will do that. To do so, lets make some assumptions. The matrix (map) has a zero for empty places (where you can move) ans negative values to indicate where the walls are (where you cannot move.). Lets also assume the matrix is bounded by walls on all four edges.

FUNCTION fill(int x, int y, int level)
 BEGIN
    map(x,y) = level
    level = level + 1
    FOR x1,y1=neighborOf(x,y)
     IF ((0 == map(x1,y1)) OR (level < map(x1,y1))
      THEN fill(x1, y1, level)
 END
MAIN BEGIN
   fill(startX, startY, 1)
   IF (0 == map(solveX, solveY))
    THEN 
      PRINT "unsolvable"
    ELSE 
      PRINT map(solveX, solveY)," steps needed to solve"
    END IF
END MAIN 

One of the drawbacks of depth first, is you might have a spot that has at least two paths to it and you might have arrived there via the longer path first. In these cases you have to back track and take the shorter path. The above code does this with the if test for level < map(x1,y1). If the next location has a larger value in it than level's current value, then it acts just like the cell is empty and moves forward (essentially implementing backtracking).

To avoid the need for back tracking/possibly visiting the same cell multiple times, you need to implement a breadth first flood fill. This means all "neighbors" of the current point must be visited before going to the next level. To do this, we are going to have to make a FIFO queue to store neighbors in. Here is fill implemented breadth first:

fill(int x, int y, int level)
 BEGIN
    level = level + 1
    FOR x1,y1=neighborOf(x,y)
       IF (0 == map(x1,y1))
        THEN 
          map(x1,y1) = level
          enqueue(x1, y1)
        END IF
    WHILE NOT EMPTY(queue)
        x1,y1 = dequeue()
        fill(x1, y1, map(x1, y1)
     END WHILE
 END

This approach can be extended to 3-D easily by using a 3-D array and checking for neighbors in a way that checks in x, y and z directions. Flood fill can also be used to count how may different low points exist in a grid.

To get a good idea, of the number of different uses for flood fill, visit Problem categories and go through the section on flood fill.