Graph: Flood Fill algorithm

Problem Statement:

You are given an image represented in 2D array.

Each integer representing pixel value of the image.

You are given a co-ordinate sr,sc and a color, you need to perform flood fill on the image starting form the co-ordinate.

You need to perform below operations:

1. Start with the starting pixel and change its color to color.

2. Perform the same process for each pixel that is directly adjacent and shares the same color as the starting pixel.

3. Complete the whole process and return the new image.

Example:

Input: Image = [[1,1,1],
                [1,1,0],
                [1,0,1]] 

sr = 1, sc = 1, color = 2

Output: [[2,2,2],
	     [2,2,0],
	     [2,0,1]]

Solution Explanation:

Solution is very simple.

We will use DFS to solve the problem.

We will start from sr, sc.

If the pixel is out of bounds, or already painted or not the original color, we stop the algo.

else, paint the node with new color and recurse its 4 neighbours

Time Complexity: O(r*c)
Space Complexity: O(r*c)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


void dfs(vector<vector<int>>& image, int i, int j,int val, int newColor)
{
    // boundary check
    if(i<0 || i>=image.size() || j<0 || j>= image[0].size() 
       || image[i][j] == newColor || image[i][j] != val)
    {
        return;
    }

    // paint with new color
    image[i][j] = newColor;

    dfs(image,i-1,j,val,newColor); // up
    dfs(image,i+1,j,val,newColor); // down
    dfs(image,i,j-1,val,newColor); // left
    dfs(image,i,j+1,val,newColor); // right
}

vector<vector<int>> solution(vector<vector<int>>& image, int sr, int sc, int newColor)
{
    int val = image[sr][sc];    
    dfs(image,sr,sc,val,newColor);     
    return image;                      
}

int main()
{
		
	vector<vector<int>>image
	{
	    {1,1,1},
	    {1,1,0},
	    {1,0,1}
	};
	
	vector<vector<int>> ans = solution(image, 1, 1, 2);
	for(auto i: ans)
	{
		for(auto j: i)
			cout << j << " ";
		cout << "\n";
	}
	
	return 0;
}

Output

2 2 2 
2 2 0 
2 0 1