Maximum of all distances to the nearest 1 cell from any 0 cell in a Binary matrix | C ++ Program to find the maximum distance from a 0 - cell to a 1 - cell ; Function to find the maximum distance ; Queue to store all 1 - cells ; Grid dimensions ; Directions traversable from a given a particular cell ; If the grid contains only 0 s or only 1 s ; Access every 1 - cell ; Traverse all possible directions from the cells ; Check if the cell is within the boundaries or contains a 1 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxDistance ( vector < vector < int > > & grid ) { queue < pair < int , int > > q ; int M = grid . size ( ) ; int N = grid [ 0 ] . size ( ) ; int ans = -1 ; int dirs [ 4 ] [ 2 ] = { { 0 , 1 } , { 1 , 0 } , { 0 , -1 } , { -1 , 0 } } ; for ( int i = 0 ; i < M ; ++ i ) { for ( int j = 0 ; j < N ; ++ j ) { if ( grid [ i ] [ j ] == 1 ) q . emplace ( i , j ) ; } } if ( q . empty ( ) || M * N == q . size ( ) ) return -1 ; while ( q . size ( ) ) { int cnt = q . size ( ) ; while ( cnt -- ) { auto p = q . front ( ) ; q . pop ( ) ; for ( auto & dir : dirs ) { int x = p . first + dir [ 0 ] ; int y = p . second + dir [ 1 ] ; if ( x < 0 x > = M y < 0 y > = N grid [ x ] [ y ] ) continue ; q . emplace ( x , y ) ; grid [ x ] [ y ] = 1 ; } } ++ ans ; } return ans ; } int main ( ) { vector < vector < int > > arr = { { 0 , 0 , 1 } , { 0 , 0 , 0 } , { 0 , 0 , 1 } } ; cout << maxDistance ( arr ) << endl ; return 0 ; }