Flood Fill

Posted: 8 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

An 'IMAGE' is represented by the 2-D array of positive integers, where each element of 2-D represents the pixel value of the image.

The given 'IMAGE' has 'N' rows and 'M' columns. You are given the location of the pixel in the image as ('X', 'Y')(0-based indexing) and a pixel value as 'P'.

Your task is to perform “flood fill” operation on the given coordinate (X, Y) with pixel value 'P'.

Let the current pixel value of ('X', 'Y') equal to C. To perform flood fill operation on the coordinate (X, Y) with pixel value 'P' you need to do the following operations in order:

1. Replace the pixel value of ('X', 'Y') with 'P'.

2. Visit all non-diagonal neighbours of ('X', 'Y') having pixel value equal to C and replace their pixel value with 'P'.

3. Non – diagonal neighbours are Up('X' - 1, 'Y'), Down('X' + 1, 'Y'), Left('X', 'Y' - 1), right('X', 'Y' + 1). Also, you cannot go out of bounds.

4. Visit all non-diagonals neighbours of coordinates visited in step 2 having pixel value equal to C and replace their pixel value with 'P'. 

5. Repeat step 2, until you have visited all neighbours
For Example:
For  'N' = 5 , 'M' = 4 , 'X' = 2 , 'Y' = 2 and 'P' = 5
Given 'IMAGE' is shown below:

[7, 1, 1, 1]
[1, 7, 7, 7]
[7, 7, 7, 0]
[7, 7, 7, 4]
[4, 4, 4, 4]

After flood fill operation we will replace all neighbour's 7s with 5.

So our 'IMAGE' will become:

[7, 1, 1, 1]
[1, 5, 5, 5]
[5, 5, 5, 0]
[5, 5, 5, 4]
[4, 4, 4, 4]
Input format:
The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test contains two space-separated integers 'N' and 'M', denoting the number of rows and columns respectively.

The second line of each test contains three space-separated integers, 'X', 'Y' and 'P', denoting starting coordinates of pixel and the new pixel value of flood fill operation.

The next 'N' lines will contain 'M' space-separated integers denoting elements of the image array.
Output format:
For each test case, return a 2D matrix/array of size N * M representing the 'IMAGE' after performing flood fill operation.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function
Constraints :
1 <= T <= 100   
1 <= N,M <= 100 
0 <= X <= N – 1
0 <= Y <= M - 1
0 <= IMAGE[i][j], P <= 10^9

Where 'IMAGE[i][j]' denotes the image matrix pixel elements.

Time limit: 1 sec
Approach 1

In this solution, we will run a dfs starting from a given coordinate ('X', ‘Y’) and visit all its adjacent elements and mark all of them by replacing their pixel value with ‘P’.

 

The steps are as follows:

 

  1. Initially declare ‘rowSize’ with ‘N’, and ‘columnSize’ with ‘M’.
  2. Check if ‘IMAGE[X][Y]’ = ‘P’ then return ‘IMAGE’.
  3. call dfs(‘IMAGE’, 'N', ‘M’, ‘X’, ‘Y’, ‘P’, ‘IMAGE[X}[Y]’) function.
  4. At last return ‘IMAGE’.

 

void dfs(‘IMAGE’, ‘N’, ‘M’, ‘currentX’, ‘currentY’, ‘P’, ‘C’):

  1. Check if current coordinate ('currentX', ‘currentY’) is out of bound or not and its pixel value equals to 'C" or not, If yes then stop dfs and return.
  2. Replace the pixel value of the current coordinate ('currentX', ‘currentY’) with ‘P’.
  3. Visit all neighbours of the current coordinate ('currentX', 'currentY') .
Try Problem