Trusted answers to developer questions
Flood fill algorithm in C++
Educative Answers TeamFlood fill is an algorithm which is used to determine the properties of the area around a particular cell. This algorithm is particularly used in the “bucket fill” tool of paint program. This tool colors the similarly colored pixels/cells with another color. This feature is famously used in a game called “Minesweeper” to identify the cleared pieces.
The algorithm:
The algorithm is passed a target cell consisting of x and y values along with a color to be filled and the current color of the cell. It proceeds as follows:
- If x or y is outside the screen, then return.
- If the color of screen[x][y] is not same as current color, then return
- Recursively call the function for north(x, y+1), south(x, y-1), east(x+1, y) and west(x-1,y).
Example:
The following code implements the algorithm mentioned above. It targets the cell [4][4] and sets the color value to “3” of every neighboring cell having the same value as cell [4][4].
#include<iostream>
using namespace std;
// Dimentions of myScreen. You may change
#define M 8
#define N 8
// A recursive function to replace
// previous color 'currColor' at '(x, y)'
// and all surrounding pixels of (x, y)
// with new color 'newColor'
void floodFill(int myScreen[][N], int x, int y, int currColor, int newColor)
{
// Base cases
if (x < 0 || x >= M || y < 0 || y >= N)
return;
if (myScreen[x][y] != currColor)
return;
if (myScreen[x][y] == newColor)
return;
// Replace the color at cell (x, y)
myScreen[x][y] = newColor;
// Recursively call for north, east, south and west
floodFill(myScreen, x+1, y, currColor, newColor);
floodFill(myScreen, x-1, y, currColor, newColor);
floodFill(myScreen, x, y+1, currColor, newColor);
floodFill(myScreen, x, y-1, currColor, newColor);
}
// It mainly finds the previous color on (x, y) and
// calls floodFill()
void findColor(int myScreen[][N], int x, int y, int newColor)
{
int currColor = myScreen[x][y];
floodFill(myScreen, x, y, currColor, newColor);
}
// Driver program to test above function
int main()
{
int myScreen[M][N] =
{
{3, 2, 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, y = 4, newColor = 3;
findColor(myScreen, x, y, newColor);
cout << "Updated myScreen : \n";
//printing screen
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << myScreen[i][j] << " ";
cout << endl;
}
return 0;
}
RELATED TAGS
flood
fill
c++
algorithm
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
