Distance of nearest cell having 1 in a binary matrix | Python3 program to find distance of nearest cell having 1 in a binary matrix . ; Making a class of graph with bfs function . ; Function to create graph with N * M nodes considering each cell as a node and each boundary as an edge . ; A number to be assigned to a cell ; If last row , then add edge on right side . ; If not bottom right cell . ; If last column , then add edge toward down . ; Else makes an edge in all four directions . ; BFS function to find minimum distance ; Printing the solution . ; Find minimum distance ; Creating a graph with nodes values assigned from 1 to N x M and matrix adjacent . ; To store minimum distance ; To mark each node as visited or not in BFS ; Initialising the value of distance and visit . ; Inserting nodes whose value in matrix is 1 in the queue . ; Calling for Bfs with given Queue . ; Printing the solution . ; Driver code
from collections import deque NEW_LINE MAX = 500 NEW_LINE N = 3 NEW_LINE M = 4 NEW_LINE g = [ [ ] for i in range ( MAX ) ] NEW_LINE n , m = 0 , 0 NEW_LINE def createGraph ( ) : NEW_LINE INDENT global g , n , m NEW_LINE k = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , m + 1 ) : NEW_LINE INDENT if ( i == n ) : NEW_LINE INDENT if ( j != m ) : NEW_LINE INDENT g [ k ] . append ( k + 1 ) NEW_LINE g [ k + 1 ] . append ( k ) NEW_LINE DEDENT DEDENT elif ( j == m ) : NEW_LINE INDENT g [ k ] . append ( k + m ) NEW_LINE g [ k + m ] . append ( k ) NEW_LINE DEDENT else : NEW_LINE INDENT g [ k ] . append ( k + 1 ) NEW_LINE g [ k + 1 ] . append ( k ) NEW_LINE g [ k ] . append ( k + m ) NEW_LINE g [ k + m ] . append ( k ) NEW_LINE DEDENT k += 1 NEW_LINE DEDENT DEDENT DEDENT def bfs ( visit , dist , q ) : NEW_LINE INDENT global g NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT temp = q . popleft ( ) NEW_LINE for i in g [ temp ] : NEW_LINE INDENT if ( visit [ i ] != 1 ) : NEW_LINE INDENT dist [ i ] = min ( dist [ i ] , dist [ temp ] + 1 ) NEW_LINE q . append ( i ) NEW_LINE visit [ i ] = 1 NEW_LINE DEDENT DEDENT DEDENT return dist NEW_LINE DEDENT def prt ( dist ) : NEW_LINE INDENT c = 1 NEW_LINE for i in range ( 1 , n * m + 1 ) : NEW_LINE INDENT print ( dist [ i ] , end = " ▁ " ) NEW_LINE if ( c % m == 0 ) : NEW_LINE INDENT print ( ) NEW_LINE DEDENT c += 1 NEW_LINE DEDENT DEDENT def findMinDistance ( mat ) : NEW_LINE INDENT global g , n , m NEW_LINE n , m = N , M NEW_LINE createGraph ( ) NEW_LINE dist = [ 0 ] * MAX NEW_LINE visit = [ 0 ] * MAX NEW_LINE for i in range ( 1 , M * N + 1 ) : NEW_LINE INDENT dist [ i ] = 10 ** 9 NEW_LINE visit [ i ] = 0 NEW_LINE DEDENT k = 1 NEW_LINE q = deque ( ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( M ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT dist [ k ] = 0 NEW_LINE visit [ k ] = 1 NEW_LINE q . append ( k ) NEW_LINE DEDENT k += 1 NEW_LINE DEDENT DEDENT dist = bfs ( visit , dist , q ) NEW_LINE prt ( dist ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 0 , 0 , 0 , 1 ] , [ 0 , 0 , 1 , 1 ] , [ 0 , 1 , 1 , 0 ] ] NEW_LINE findMinDistance ( mat ) NEW_LINE DEDENT