Last Updated: 3 Dec, 2021

Border Color

Moderate

Asked in company

Solve now

Problem statement

You are given an N*M matrix where the cell (i,j) is colored by MATRIX[i][j]. You have to color the border of the connected component which contains the cell (ROW, COL) with the color NEW_COLOR. Two squares belong to the same connected component if they have the same color and are next to each other in any of the 4 directions (top, down, left, right).

Example:-

N = 2, M = 2, NEW_COLOR = 3, ROW = 0, COL = 0 
MATRIX = [[1,1],[1,2]]
ANSWER:- The answer should be [[3,3],[3,2]] because the connected component is the cells with indices (0,0),(0,1) and (1,0).

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains five integers ‘N’, ‘M’, ‘NEW_COLOR’, ‘ROW’, ‘COL’ denoting the number of rows and columns in the matrix, the new color that will be applied to the borders of the connected component, and the coordinates of the cell which the connected component contains respectively.

The next ‘N’ lines of every test case contain ‘M’ integers which denote MATRIX[i][j], the color cell (i,j) is currently colored.

Output Format :

For each test case, return a matrix of N*M with the colors of the cells updated..

The output of each test case should be printed in a separate line.

Note :

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 5
1 <= N <= 500
1 <= M <= 500
1 <= MATRIX[i][j] <= 10^9
1 <= NEW_COLOR <= 10^9
1 <= ROW <= N
1 <= COL <= M

Time Limit =  1sec

Solve now

Approaches

01 Approach

Use breadth-first search to find which cells are connected with (row, col). Then check whether those cells lie on the border of the connected component or not. If yes, change their colors.

Algorithm:-

Initialize an empty QUEUE. Insert (row, col) in the queue.
Initialize a 2D array named ANS with N*M dimensions.
Start a while loop while the QUEUE is not empty.
1. Pop-out the first element in the QUEUE.
2. If the neighbor of the currently popped cell is of the same color, mark it as connected and add it to the QUEUE.
Iterate from 0 to N(Let’s say the iterator is i).
1. Iterate from 0 to M.(Let’s say the iterator is j).
  1. Count the number of neighboring cells with the same color.
  2. If the count of such cells is less than 4 and the cell is connected, set ANS[i][j] as NEW_COLOR.
  3. Otherwise, update ANS[i][j] as MATRIX[i][j].
Return the ANS.

Solve now