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

Question

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.

Accepted Answer

Given a binary matrix, find the distance of the nearest cell having 1 in the matrix for each cell.

Use BFS to traverse the matrix and find the nearest cell having 1 for each cell.
Initialize the output matrix with maximum possible distance.
If the current cell has 1, distance is 0, else update distance based on the nearest cell having 1.

Accepted Answer

The better approach is to do a BFS starting from all the 1s in the given matrix. The distance of all the 1s is zero and for all the adjacent the minimum distance is one more than this.

Create a queue of Coordinates, that is used to store the (row, column) of an element. Create an array ans of size same as array matrix.
Traverse through all the elements of the matrix and push the coordinates of elements that are 1 into the queue.
Initialize a variable minDistance as 0. While queue is not empty repeat steps 4 and 5.
Initialize a variable size as size of the queue. Run a loop for i equals 0 to size(not included). At every iteration pop out an element from the queue. Set ans[row][col] as minDistance, and enqueue all the valid adjacents of this element that are 0 in the matrix array and set them as 1 in the matrix array.
Increment minDistance.
Print the ans array.

Accepted Answer

Brute Force

Traverse the matrix for all N*M cells one by one.
For every cell find the closest cell which contains 1.
Update the minimum distance.
Fill the minimum distance in the matrix.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space required.

Time Complexity: OtherExplanation:

O(N^2 * M^2), where ‘N’ is the number of rows and ‘M’ is the number of columns of the matrix.

For every cell, all N*M cells are traversed.And there are a total of N*M cells in the matrix. So the overall time complexity will be O(N^2 * M^2).

C++ (g++ 5.4)

/*

    Time complexity: O(N^2*M^2)

    Space complexity: O(1)



    where N is the number of rows and M is the number of columns.

*/



#include 



vector < vector < int > > nearest(vector < vector < int >> & mat, int n, int m) {

    // Initialize the answer matrix with INT_MAX.

    vector < vector < int >> dist(n, vector < int > (m, INT_MAX));



    // For each cell

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            /* 

                Traversing the whole matrix to find the minimum distance.

            */

            for (int k = 0; k < n; k++) {

                for (int l = 0; l < m; l++) {

                    // If cell contain 1, check for minimum distance.

                    if (mat[k][l] == 1) {

                        dist[i][j] = min(dist[i][j], abs(i - k) + abs(j - l));

                    }

                }

            }

        }

    }

    return dist;

}

Java (SE 1.8)

/*

    Time complexity: O(N^2*M^2)

    Space complexity: O(1)



    where N is the number of rows and M is the number of columns.

*/



import java.util.ArrayList;



public class Solution {

    public static ArrayList < ArrayList < Integer >> nearest(ArrayList < ArrayList < Integer >> mat, int n, int m) {



        // Initialize the answer matrix with INT_MAX.

        ArrayList < ArrayList < Integer >> dist = new ArrayList < ArrayList < Integer >> ();

        for (int i = 0; i < n; i++) {

            ArrayList < Integer > temp = new ArrayList < Integer > ();

            for (int j = 0; j < m; j++) {

                temp.add(Integer.MAX_VALUE);

            }

            dist.add(temp);

        }



        // For each cell

        for (int i = 0; i < n; i++) {



            for (int j = 0; j < m; j++) {



                // Traversing the whole matrix to find the minimum distance.

                for (int k = 0; k < n; k++) {



                    for (int l = 0; l < m; l++) {



                        // If cell contain 1, check for minimum distance.

                        if (mat.get(k).get(l).intValue() == 1) {

                            dist.get(i).set(j, Math.min(dist.get(i).get(j), Math.abs(i - k) + Math.abs(j - l)));

                        }

                    }

                }

            }

        }

        return dist;

    }

}

Python (3.5)

'''

    Time complexity: O(N^2*M^2)

    Space complexity: O(1)



    where N is the number of rows and M is the number of columns.

'''



def nearest(mat, n, m):

    # Initialize the answer matrix with INT_MAX.

    dist = [[9999999 for i in range(m)] for j in range(n)]



    # For each cell

    for i in range(n):

        for j in range(m):



            '''

                Traversing the whole matrix to find the minimum distance.

            '''

            for k in range(n):

                for l in range(m):

                    # If cell contain 1, check for minimum distance.

                    if (mat[k][l] == 1):

                        dist[i][j] = min(dist[i][j], abs(i - k) + abs(j - l))

    

    return dist

Accepted Answer

Breadth-First Search

The basic idea of this approach is to use multi-source breadth first search. We will do bfs considering all the cells with value 1 as starting nodes. We can use an auxiliary queue to perform BFS.

Create an empty queue.
Traverse the whole matrix and insert the coordinates of all 1’s in the queue in the form of a pair.
Now do a BFS traversal of the graph using the above created queue.
Run a loop till the queue is not empty.
Extract the front node of the queue and pop it and insert all its adjacent and unmarked elements by moving one step at a time in any of the four directions.
Update the minimum distance as the distance of current node +1 and insert the coordinates of the next element in the queue.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns of the matrix.

To store every element in the matrix O(M*N) space is required.

Time Complexity: O(m*n) - For 2d arraysExplanation: