Flood Fill Algorithm

Flood Fill Algorithm

We might have encountered this at many places. Paint tool is one such example, when we say fill with color in paint, it fills the neighboring areas with the same color.
For examples in the below image when we do a fill color on the white area, we would want all the neighboring white areas to be colored.

The algorithm is very simple. We start with the user selected grid, fill it with color and then check the top, bottom, right and left grid and fill them as well. We do this recursively to achieve the end result.

Below is the procedure

floodFill(vector<vector<int>grid>, x, y, oldColor, newColor)

• If x or y is outside the grid, then return.
• If color of grid[x][y] is not same as oldColor, then return
• do the same for top, down, right and left.

    floodFillUtil(grid, x+1, y, oldColor, newColor);
    floodFillUtil(grid, x-1, y, oldColor, newColor);
    floodFillUtil(grid, x, y+1, oldColor, newColor);
    floodFillUtil(grid, x, y-1, oldColor, newColor); 

Lets see a C++ implementation for this algorithm

	#include<vector>
	#include<iostream>
	using namespace std;
	void floodFill(vector<vector<int>>&grid, int x, int y, int oldColor, int newcolor)
	{
	//check boundary conditions
	if (x < 0 || y < 0 || x >= grid.size() || y >= grid.size())
	return;
	//check if current point is previouscolor
	if (grid[x][y] != oldColor)
	return;
	if (grid[x][y] == newcolor)
	return;
	grid[x][y] = newcolor;
	//left
	floodFill(grid,x-1,y,oldColor, newcolor);
	//right
	floodFill(grid, x +1, y, oldColor, newcolor);
	//top
	floodFill(grid, x, y -1, oldColor, newcolor);
	//bottom
	floodFill(grid, x, y + 1, oldColor, newcolor);
	}
	void printgrid(vector<vector<int>>&grid)
	{
	for (int x = 0; x < grid.size(); x++)
	{
	for (int y = 0; y < grid.size(); y++)
	{
	cout << grid[x][y];
	}
	cout << endl;
	}
	}
	int main()
	{
	vector<vector<int>>grid =
	{
	{ 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 1, 1, 1, 1, 1, 1, 0, 0 },
	{ 1, 0, 0, 1, 1, 0, 1, 1 },
	{ 1, 2, 2, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 0, 1, 0 },
	{ 1, 1, 1, 2, 2, 2, 2, 0 },
	{ 1, 1, 1, 1, 1, 2, 1, 1 },
	{ 1, 1, 1, 1, 1, 2, 2, 1 },
	};
	int x = 4;
	int y = 4;
	printgrid(grid);
	//convert all 2s to 9
	floodFill(grid,x,y,grid[x][y],9);
	printgrid(grid);
	return 0;
	}

view raw FloodFill.cpp hosted with ❤ by GitHub