Flood fill algorithm

Flood fill algorithm helps in visiting each and every point in a given area. It determines the area connected to a given cell in a multi-dimensional array. Following are some famous implementations of flood fill algorithm

Bucket Fill in Paint

Clicking in an area with this tool selected fills that area with the selected color.

Solving a Maze

Given a matrix with some starting point, and some destination with some obstacles in between, this algorithm helps to find out the path from source to destination

 

Minesweeper

When a blank cell is discovered, this algorithm helps in revealing neighboring cells. This step is done recursively till cells having numbers are discovered.

Flood fill algorithm can be simply modeled as graph traversal problem, representing the given area as a matrix and considering every cell of that matrix as a vertex that is connected to points above it, below it, to right of it, and to left of it and in case of 8-connections, to the points at both diagonals also. For example, consider the image given below.

                  

It clearly shows how the cell in the middle is connected to cells around it. For instance, there are 8-connections like there are in Minesweeper (clicking on any cell that turns out to be blank reveals 8 cells around it which contains a number or are blank). The cell (1,1),(1,1) is connected to (0,0),(0,0), (0,1),(0,1), (0,2),(0,2), (1,0),(1,0), (1,2),(1,2), (2,0),(2,0), (2,1),(2,1), (2,2),(2,2).

In general any cell (x,y) ,(x,y) is connected to (x−1,y−1),(x−1,y−1), (x−1,y),(x−1,y), (x+1,y),(x+1,y), (x,y−1),(x,y−1), (x,y+1),(x,y+1), (x+1,y−1),(x+1,y−1), (x+1,y),(x+1,y), (x+1,y+1)(x+1,y+1)

Flood fill is a search that starts at a point and finds the areas connected to the start point. For example, the "bucket fill" in Photoshop or MS Paint uses flood fill to fill in the connecting areas of the same color.

Flood fill can be implemented using a BFS or DFS.

Bucket Fill

Given an N x M matrix and a start point and two colors (src and dst), we want to replace all the cells in the matrix that are connected to the start point with the color src and change to color dst as well as output the number of cells changed.

Example

                  

We use bucket fill in the top left corner of the bitmap to fill everything with the same color as the cell.

                  

A numeric representation of the bitmap before bucket fill:

                  

Numeric representation of the bitmap after bucket fill in the left: