Binary Matrix

Posted: 18 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

You are given a matrix ‘MAT’ consisting of ‘N’ rows and ‘M’ columns. Let (i, j) represent the cell at the intersection of the ith row and the jth column. Each cell of the matrix ‘MAT’ has either integer 0 or 1. For each cell in ‘MAT’, you have to find the Manhattan distance of the nearest cell from this cell that has the integer 0. The nearest cell will be the cell having the minimum Manhattan distance from it.

Manhattan distance between two cells, (p1, q1) and (p2, q2) is |p1 - p2| + |q1 - q2|.

You should return a matrix consisting of ‘N’ rows and ‘M’ columns, where the cell (i, j) represents the Manhattan distance of the nearest cell from the cell (i, j) in ‘MAT’ that has integer 0.

Note
1. There is at least one cell having the integer 0 in the given matrix.
Example:
Consider the following 2*3 matrix ‘MAT’:
                 [0, 1, 1]
                 [0, 1, 1]

Here, the nearest cell having the integer 0 from the cell (0, 0) is the cell (0, 0) itself. The Manhattan distance between them is |0 - 0| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (0, 1) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (0, 2) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |2 - 0| = 2.

The nearest cell having the integer 0 from the cell (1, 0) is cell (1, 0) itself. The Manhattan distance between them is |1 - 1| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (1, 1) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (1, 2) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |2 - 0| = 2.
Thus we should return matrix:

                [0, 1, 2]
                [0, 1, 2]
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line of each test case consists of two single space-separated integers ‘N’ and ‘M’ representing the number of rows and columns in matrix ‘MAT’

Then next ‘N’ lines follow in each test case. Each of these ‘N’ lines consists of ‘M’ single space-separated integers (either 0 or 1).  These ‘N’ lines together represent the matrix ‘MAT’. 
Output format :
For each test case, print ‘N’ lines each of which consists of ‘M’ space-separated integers. The jth integer in the ith line will be the Manhattan distance of the nearest cell from the cell (i, j) in  ‘MAT’ that has integer 0.

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

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
0 <= MAT[i][j] <= 1


Where ‘T’ is the total number of test cases,  ‘N’ and ‘M’ denote the number of rows and columns in the given matrix ‘MAT’, and MAT[i][j] is the element of the given matrix at cell (i, j). 

Time limit: 1 sec.
Approach 1

This approach is straightforward, we will make a matrix ‘DIST’ of dimension N * M and initially fill it with infinity.  Then we iterate over each cell of the matrix ‘MAT’ and if we find any cell in ‘MAT’ that has integer 0, then we update the value of each cell in matrix ‘DIST’ with the minimum of its current value and its Manhattan distance from the current cell of ‘MAT’.

 

Algorithm

  • Create a matrix ‘DIST’ of dimension N * M and fill it with infinity.
  • Run a loop where ‘i’ ranges from 0 to ‘N’ - 1.
    • Run a loop where ‘j’ ranges from 0 to ‘M’ - 1.
      • If  ‘MAT[i][j]’ = 0,  then run a nested loop where ‘k’ ranges from 0 to ‘N’-1 and for each ‘k’‘l’ ranges from 0 to ‘M’-1. for each ‘k’, ‘l’ do ‘DIST[k][l]’ = min(‘DIST[k][l]’, |i-k| + |j-l|) where |x| is the absolute value of ‘x’.
  • Return ‘DIST’.
Try Problem