Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

flood
fill
java
algorithm
c++

What is the Flood fill algorithm?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The flood fill algorithm is used to determine the properties of the area around a particular cell in a block. The algorithm is implemented in the bucket fill tool of the Microsoft Paint program, which colors the similarly colored pixels, or cells, with another color.

The algorithm is also used in the famous Minesweeper game to identify cleared pieces.

svg viewer

The algorithm

The algorithm needs the following data to proceed: the x and y coordinates of the target cell, its current color, and the desired color. It proceeds as follows:

  1. If xx or yy is outside the screen, then return.
  2. If color of screen[xx][yy] is not same as current color, then return
  3. Call recursively for north(xx, yy+1), south(xx, yy-1), east(xx+1, yy) and west(xx-1,yy).

Example

The code below implements the algorithm mentioned above. It targets the cell [4][4] and, for every neighboring cell that has the same value as cell [44][44], it sets the color value to “3”.

//flood fill algorithm implemented in C++
#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] != currColor)
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},
};
//print initial screen
cout << "Initial myScreen : \n";
for (int i=0; i<M; i++)
{
for (int j=0; j<N; j++)
cout << myScreen[i][j] << " ";
cout << endl;
}
int x = 4, y = 4, newColor = 3;
findColor(myScreen, x, y, newColor);
cout<<endl;
cout << "Updated myScreen : \n";
//printing updated 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
java
algorithm
c++
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring