Maximum of all distances to the nearest 1 cell from any 0 cell in a Binary matrix | Function to find the maximum distance ; Set up top row and left column ; Pass one : top left to bottom right ; Check if there was no " One " Cell ; Set up top row and left column ; Past two : bottom right to top left ; Driver code
def maxDistance ( grid ) : NEW_LINE INDENT if ( len ( grid ) == 0 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT N = len ( grid ) NEW_LINE INF = 1000000 NEW_LINE if grid [ 0 ] [ 0 ] == 1 : NEW_LINE INDENT grid [ 0 ] [ 0 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT grid [ 0 ] [ 0 ] = INF NEW_LINE DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT if grid [ 0 ] [ i ] == 1 : NEW_LINE INDENT grid [ 0 ] [ i ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT grid [ 0 ] [ i ] = grid [ 0 ] [ i - 1 ] + 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT if grid [ i ] [ 0 ] == 1 : NEW_LINE INDENT grid [ i ] [ 0 ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT grid [ i ] [ 0 ] = grid [ i - 1 ] [ 0 ] + 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , N ) : NEW_LINE INDENT for j in range ( 1 , N ) : NEW_LINE INDENT if grid [ i ] [ j ] == 1 : NEW_LINE INDENT grid [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT grid [ i ] [ j ] = min ( grid [ i - 1 ] [ j ] , grid [ i ] [ j - 1 ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT if ( grid [ N - 1 ] [ N - 1 ] >= INF ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT maxi = grid [ N - 1 ] [ N - 1 ] NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT grid [ N - 1 ] [ i ] = min ( grid [ N - 1 ] [ i ] , grid [ N - 1 ] [ i + 1 ] + 1 ) NEW_LINE maxi = max ( grid [ N - 1 ] [ i ] , maxi ) NEW_LINE DEDENT for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT grid [ i ] [ N - 1 ] = min ( grid [ i ] [ N - 1 ] , grid [ i + 1 ] [ N - 1 ] + 1 ) NEW_LINE maxi = max ( grid [ i ] [ N - 1 ] , maxi + 1 ) NEW_LINE DEDENT for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT grid [ i ] [ j ] = min ( grid [ i ] [ j ] , min ( grid [ i + 1 ] [ j ] + 1 , grid [ i ] [ j + 1 ] + 1 ) ) NEW_LINE maxi = max ( grid [ i ] [ j ] , maxi ) NEW_LINE DEDENT DEDENT if maxi == 0 : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return maxi NEW_LINE DEDENT DEDENT arr = [ [ 0 , 0 , 1 ] , [ 0 , 0 , 0 ] , [ 0 , 0 , 0 ] ] NEW_LINE print ( maxDistance ( arr ) ) NEW_LINE