Everything about Flood Fill Algorithm || Graphs

Visualizing this algo !

Flood fill, also called seed fill, is an algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. — Wikipedia

How does it work (easy logic ) ?

The problem is pretty simple and usually follows these steps:

  1. Take the position of the starting point.
  2. Decide wether you want to go in 4 directions (N, S, W, E) or 8 directions (N, S, W, E, NW, NE, SW, SE) (depends on the problem)
  3. Choose a replacement color and a target color.
  4. Travel in those directions.
  5. If the tile you land on is a target, reaplce it with the chosen color.
  6. Repeat 4 and 5 until you’ve been everywhere within the boundaries.

Let’s solve a famous interview problem on graphs where this algorithm is used

Question:

In MS-Paint, when we take the brush to a pixel and click, the color of the region of that pixel is replaced with a new selected color. Following is the problem statement to do this task.
Given a 2D screen arr[][] where each arr[i][j] is an integer representing the color of that pixel, also given the location of a pixel (X, Y) and a color C, the task is to replace the color of the given pixel and all the adjacent same-colored pixels with the given color.

Example testcase

Input
screen[M][N] = {{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},
};
x = 4, y = 4, newColor = 3
* The values in the given 2D screen
indicate colors of the pixels.
* x and y are coordinates of the brush,
* newColor is the color that should replace the previous color on
screen[x][y] and all surrounding pixels with same color.

Output:
Screen should be changed to following.
screen[M][N] = {{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, 3, 3, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 3, 3, 0},
{1, 1, 1, 1, 1, 3, 1, 1},
{1, 1, 1, 1, 1, 3, 3, 1},
};

Approach

  • This question can be solved using either Recursion(DFS) or BFS.
  • Using Recursion is always easy in path/2D array problems so let us do this with dfs !
  • The idea is simple, we first replace the color of the current pixel with the new color, then recur for 4 surrounding points. The following is a detailed algorithm.

Base Case :

  • if x,y are not in the 2D matrix i.e if(x<0 || y<0 || x>=m || y>=n)
  • or if matrix[x][y] does not contain the current(previous) color
  • or matrix[x][y] is already filled with the new color

Simply return in all the above 3 base cases

Code :

void dfs( vector<vector<int>> & image, int x, int y, int m, int n, int prevColor, int newColor) {

if (x < 0 || y < 0 || x >= m || y >= n ) return;
if (image[x][y] != prevColor) return;
if (image[x][y] == newColor) return;

image[x][y] = newColor;

dfs(image, x + 1, y, m, n, prevColor, newColor);
dfs(image, x, y + 1, m, n, prevColor, newColor);
dfs(image, x - 1, y, m, n, prevColor, newColor);
dfs(image, x, y - 1, m, n, prevColor, newColor);
}
vector < vector < int >> floodFill(vector < vector < int >> & image, int x, int y, int newColor) { int prevColor = image[x][y];
int m = image.size(), n = image[0].size();

dfs(image, x, y, m, n, prevColor, newColor);

return image;
}

Expected Time Compelxity: O(n*m)

--

--

--

A full stack developer and a curious person

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Encapsulation in C#

Odyssey Data Value Mining Tool | A Next-generation Computing Engine for AnalyticDB for PostgreSQL

Step into the GAMESTATE!

Learn to code. Learn Python.

Status Quo and Technology Trend Report of Java

Testing website using Docker, Jenkins and GitHub

10 Hidden Features You Can Find In Android Developer Options

Revoking tokens in Azure AD B2C

Revoked image

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Vidhu Verma

Vidhu Verma

A full stack developer and a curious person

More from Medium

Efficient solution to Sherlock and Anagrams (HackerRank)

Time Complexity Analysis

Real-world Applications of Tree Data Structures

Everything you want to know about the Stanford part-time MSCS