Solving Problems with Recursion - The Flood Fill Algorithm
(Page 4 of 10 )
Now, let's turn our attention to a totally different problem. We are working on a 2D drawing package, and we want to make a bucket fill tool similar to that found in Microsoft Paint. The user selects a color, clicks on a point, and the color spreads to fill the area with this color. Have a look at this figure.
Fig 2. We need to write a program to flood fill a shape
We want to write a function to implement this feature. We are given a 2 dimensional array of colors, a point to start painting from, and a color. We should fill the fill area with the color as mentioned above.
There is no easy non-recursive solution to this problem, but we can solve this recursively in just 8 lines of code. How? The idea is simply to make a flood fill from a point do the following:
- If the point we want to color is already filled, don't do anything and stop, else color it.
- If the point above it is not colored, call flood fill from that point (recursive step).
- If the point to the right is not colored, call flood fill from that point (recursive step).
- If the point to the left is not colored, call flood fill from that point (recursive step).
- If the point below it is not colored, call flood fill from that point (recursive step).
Now, you see, the whole solution is just 5 steps, and 4 of them are recursive calls. It is important to understand how this actually works.
class Canvas
{
byte board[][]=new byte[100][100];
public void Fill(int x,int y,byte c)
{
if(board[x][y]==c) return;
board[x][y]=c;
if(x<99&&board[x+1][y]!=c)
Fill(x+1,y,c);
if(x>0&&board[x-1][y]!=c)
Fill(x-1,y,c);
if(y<99&&board[x][y+1]!=c)
Fill(x,y+1,c);
if(y>0&&board[x][y-1]!=c)
Fill(x,y-1,c);
}
}
I have tried to make the code simpler by fixing width and height. But, of course, it is easy to generalize the code to different sizes and color formats.
Next: How it Works >>
More Practices Articles
More By Mohamed Saad
/ 32 
