Distance Of Nearest Cell Having 1 In A Binary Matrix

You have been given a binary matrix 'MAT' containing only 0’s and 1’s of size N x M. You need to find the distance of the nearest cell having 1 in the matrix for each cell.

The distance is calculated as |i1 – i2| + |j1 – j2|, where i1, j1 are the coordinates of the current cell and i2, j2 are the coordinates of the nearest cell having value 1.

Note :

You can only move in four directions which are : Up, Down, Left and Right.

For example :

If N = 3, M = 4

and mat[ ][ ] = { 0, 0, 0, 1,
                  0, 0, 1, 1,
                  0, 1, 1, 0 }

then the output matrix will be

3  2  1  0
2  1  0  0
1  0  0  1

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ which denotes the size of the matrix.

The ‘N’ lines of each test case contain ‘M’ space-separated elements of the matrix.  

Output Format:

For each test case, print a matrix of the same size containing the distance of the nearest cell having ‘1’ for each cell.

Note:

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

Constraints:

1 <= T <= 5
1 <= N <= 2*10^2
1 <= M <= 2*10^2

Where ‘T’ is the number of test cases, ‘N’ is the number of rows in the matrix and ‘M’ is the number of columns in the matrix.