Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

flood
fill
c++
algorithm

Flood fill algorithm in C++

Educative Answers Team

Flood 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.

svg viewer

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:

  1. If x or y is outside the screen, then return.
  2. If the color of screen[x][y] is not same as current color, then return
  3. 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