Maximum of all distances to the nearest 1 cell from any 0 cell in a Binary matrix | Java 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
import java . util . * ; class GFG { static class pair { int first , second ; public pair ( int first , int second ) { this . first = first ; this . second = second ; } } static int maxDistance ( int [ ] [ ] grid ) { Queue < pair > q = new LinkedList < pair > ( ) ; int M = grid . length ; int N = grid [ 0 ] . length ; int ans = - 1 ; int dirs [ ] [ ] = { { 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 . add ( new pair ( i , j ) ) ; } } if ( q . isEmpty ( ) || M * N == q . size ( ) ) return - 1 ; while ( q . size ( ) > 0 ) { int cnt = q . size ( ) ; while ( cnt -- > 0 ) { pair p = q . peek ( ) ; q . remove ( ) ; for ( int [ ] 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 ] > 0 ) continue ; q . add ( new pair ( x , y ) ) ; grid [ x ] [ y ] = 1 ; } } ++ ans ; } return ans ; } public static void main ( String [ ] args ) { int [ ] [ ] arr = { { 0 , 0 , 1 } , { 0 , 0 , 0 } , { 0 , 0 , 1 } } ; System . out . print ( maxDistance ( arr ) + "NEW_LINE"); } }