Everything about Flood Fill Algorithm || Graphs

Visualizing this algo !

One of the most beautiful & perhaps the easiest algorithm we could ever come across

It is a close resemblance to the bucket tool in MS paint

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)