Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 12 Jan, 2021

Moderate

```
Two pixels are adjacent if they are connected to each other in any of the four directions: up, down, left, or right.
Diagonal pixels are not considered adjacent.
```

```
Consider the image of size 4*4, shown below (left). Let the coordinates of the starting pixel are (1, 2) and the new color is 8. The starting pixel, highlighted with red color, has a pixel value of 3.
On replacing the given pixel and all adjacent same-colored pixels with the new color we get the new image, shown below (right). The modified pixels are highlighted with green color.
```

```
The first line of input contains an integer ‘T’ representing the number of test cases.
The first line of every test case contains two space-separated integers ‘M’ and ‘N’ representing the number of rows and columns in the image.
Each of the next ‘M’ lines contains ‘N’ space-separated integers denoting the pixel values of the image.
The next line contains three space-separated integers ‘X’, ‘Y’, and ‘C’ denoting the row and column of the starting pixel and the new color, respectively.
```

```
For each test case, the newly colored image is printed in the form of an M * N Matrix.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 100
1 <= M, N <= 50
0 <= X < M
0 <= Y < N
1 <= Image[i][j], C <= 10^5
Time Limit: 1 sec
```

- Starting from the given pixel let's traverse the image using recursion.
- The idea is to replace the colour of the starting pixel with the new colour and repeat the same procedure for the adjacent same coloured pixels.
- During the traversal, we do not replace the colour of the current pixel if:
- It has a different colour than the starting pixel.
- Or if it has already been replaced with a new colour.

- In this way, we generate a new image.
- This approach is the same as applying DFS on the given image.

Algorithm:

- Start with the given pixel.
- Base Condition 1: If the pixel has a different color than the starting pixel, return.
- Base Condition 2: If the pixel has already been replaced with the new color, return.
- Replace the colour of the current pixel with the new colour.
- Recur for the adjacent pixels (up, down, left and right).
- Return the new image.

This approach is similar to the previous one but instead of using recursion/DFS, we use BFS to traverse the image.

Algorithm:

- Create an empty queue that can hold coordinates of the pixel.
- Initialize the queue by pushing the starting coordinates.
- Repeat the following steps until the queue becomes empty:
- Pop the top coordinates from the queue. This will be the current pixel which we will be exploring.
- If the current pixel has not been colored, then change its color to the new color and push the adjacent pixels (up, down, left, and right) into the queue.

- When the queue becomes empty, we have changed the color of all the required pixels. Hence, return the new image.

Similar problems