Last Updated: 3 Dec, 2020
Maximum 0-1 Distance
Hard
Asked in company
You are given an N*M binary matrix, considering for every 0-cell(cell with value = 0) the distance from this cell to its nearest 1-cell(cell with value = 1) is 'di', you need to find the maximum value of 'di' among all values of 'di'. Formally, if the minimum distance from an 'ith' 0-cell to any 1-cell is ‘di’, you need to find max(di), where i belongs to the set of all 0-cells in the matrix.
Distance between cells (i,j) and (a,b) is given as (|i-a| + |j-b|) i.e the manhattan distance is considered here.
Here, the arrows starting from the 0-cell’s point towards their corresponding nearest one cell, and among all of these, the arrow in purple and orange gives the maximum distance, i.e., 2.
Note:
1) Binary matrix of size N*M is a matrix with N rows and M columns, in which all the cells have either value 0 or 1.
2) Nearest 1-cell from a 0-cell is the cell that contains 1 and is at least a distance from the 0-cell being considered among all the other cells. For example consider the matrix {{0,1},{0,1}}. Here the nearest 1-cell for the 0-cell at index(0,0) is the 1-cell at index (0,1) because this cell is at least distance from the 0-cell being considered as the distance from the other 1-cell at index(1,1) is 2, whereas the distance from the 1-cell at index (0,1) is 1.
3) If there are no 1-cells or no 0-cells in the matrix, return -1.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow:
The first line of each test case contains two space-separated integers, 'N' and 'M', where 'N' is the number of rows in the given matrix and 'M' is the number of columns in the given matrix.
Then 'N' lines follow for each test case:
Each line contains 'M' space-separated integers(either 1 or 0).
For more clarity, please refer to the sample input.
Output Format:
Each test case's the only line of output consists of an integer 'X', denoting the maximum possible distance from a 0-cell to its nearest 1-cell.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 100
1 <= M <= 100
where 'T' is the number of test cases, 'N' is the number of rows in the given matrix, and 'M' is the number of columns in the given matrix.
Time Limit: 1 sec.
Approaches
- Before starting with the main algorithm, let's look at the conditions when the answer will be -1. There are only two such conditions:
- If all the cells are 1-cell, then, in this case, return -1 as the answer.
- If all the cells are 0-cell, then also return -1 as the answer.
- Our problem is to find the maximum distance from a 0-cell to the nearest 1-cell, so what we can do is store the positions of all the 1-cells in a vector of pairs by iterating through the matrix.
- Initialize variable answer to 0 before proceeding further.
- Now once again, iterate through each cell of the matrix. If the cell being traversed has a value of 1, then skip that cell, but if the value of the cell being traversed is 0, then run a nested loop and calculate the distance of this 0-cell from all the 1-cells stored in the vector before and get the minimum distance. Now this distance will be the distance from the 0-cell being traversed and its nearest 1-cell.
- Since we have to calculate the maximum of all such distances, Thus after finding the nearest distance for any 0-cell update answer as answer = max(answer, nearest distance found).
- After completing the above steps, return the answer because it will contain the max distance between a 0-cell and its nearest 1-cell.
- Before starting with the main algorithm, let's look at the conditions when the answer will be -1. There are only two such conditions:
- If all the cells are 1-cell, then, in this case, return -1 as the answer.
- If all the cells are 0-cell, then also return -1 as the answer.
- The idea is to perform a multisource breadth-first search from all the 1-cells and find the distance to all 0-cells. The number of levels of this bfs will be our answer.
- Before starting with the traversal, make a queue of pairs ( queue < pair<int, int> >) and insert the positions of all the 1-cells in the given binary matrix and a variable named level count initialized to 0.
- Now run a loop until the queue is empty:
- Store the current size of the queue in a variable( say X) to count the number of elements that need to be popped from the queue at this level.
- Now pop X elements from the queue, and for each popped element check if there is any 0-cell adjacent to it,i.e if suppose the popped cell is (i,j) then the cells adjacent to it are (i+1,j), (i-1,j), (i,j+1), (i,j-1). And if there are any 0-cell, then insert their position into the queue of pairs and make them equal to 1(to know that they have been visited).
- After traversing the level(i.e., Popping X elements from the queue), increase the variable levelCount by 1.
- After coming out of the loop, return the levelCount-1 because the first level is level-0, not 1.