Maximum of all distances to the nearest 1 cell from any 0 cell in a Binary matrix | 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
def maxDistance ( grid ) : NEW_LINE INDENT q = [ ] NEW_LINE M = len ( grid ) NEW_LINE N = len ( grid [ 0 ] ) NEW_LINE ans = - 1 NEW_LINE dirs = [ [ 0 , 1 ] , [ 1 , 0 ] , [ 0 , - 1 ] , [ - 1 , 0 ] ] NEW_LINE for i in range ( M ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT if ( grid [ i ] [ j ] == 1 ) : NEW_LINE INDENT q . append ( [ i , j ] ) NEW_LINE DEDENT DEDENT DEDENT if ( len ( q ) == 0 or M * N == len ( q ) ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT while ( len ( q ) > 0 ) : NEW_LINE INDENT cnt = len ( q ) NEW_LINE while ( cnt > 0 ) : NEW_LINE INDENT p = q [ 0 ] NEW_LINE q . pop ( ) NEW_LINE for Dir in dirs : NEW_LINE INDENT x = p [ 0 ] + Dir [ 0 ] NEW_LINE y = p [ 1 ] + Dir [ 1 ] NEW_LINE if ( x < 0 or x >= M or y < 0 or y >= N or grid [ x ] [ y ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT q . append ( [ x , y ] ) NEW_LINE grid [ x ] [ y ] = 1 NEW_LINE DEDENT cnt -= 1 NEW_LINE DEDENT ans += 2 NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ [ 0 , 0 , 1 ] , [ 0 , 0 , 0 ] , [ 0 , 0 , 1 ] ] NEW_LINE print ( maxDistance ( arr ) ) NEW_LINE