Check if a path exists for a cell valued 1 to reach the bottom right corner of a Matrix before any cell valued 2 | Python3 program for the above approach ; Function to check if cell with value 1 doesn 't reaches the bottom right cell or not ; Number of rows and columns ; Initialise the deque ; Traverse the matrix ; Push 1 to front of queue ; Push 2 to back of queue ; Store all the possible direction of the current cell ; Run multi - source BFS ; Get the front element ; If 1 reached corner first ; Insert new poin queue ; If 1 can 't reach the bottom  right then return false ; Driver Code ; Given matrix ; Function call
from collections import deque NEW_LINE def reachesBottom ( a ) : NEW_LINE INDENT n = len ( a ) NEW_LINE m = len ( a [ 0 ] ) NEW_LINE q = deque ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( m ) : NEW_LINE INDENT if ( a [ i ] [ j ] == 1 ) : NEW_LINE INDENT q . appendleft ( [ i , j , 1 ] ) NEW_LINE DEDENT elif ( a [ i ] [ j ] == 2 ) : NEW_LINE INDENT q . append ( [ i , j , 2 ] ) NEW_LINE DEDENT a [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT dx = [ - 1 , 0 , 1 , 0 ] NEW_LINE dy = [ 0 , 1 , 0 , - 1 ] NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT front = q . popleft ( ) NEW_LINE i = front [ 0 ] NEW_LINE j = front [ 1 ] NEW_LINE t = front [ 2 ] NEW_LINE if ( a [ i ] [ j ] ) : NEW_LINE INDENT continue NEW_LINE DEDENT a [ i ] [ j ] = 1 NEW_LINE if ( t == 1 and ( i == n - 1 and j == m - 1 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT for d in range ( 4 ) : NEW_LINE INDENT ni = i + dx [ d ] NEW_LINE nj = j + dy [ d ] NEW_LINE if ( ni >= 0 and ni < n and nj >= 0 and nj < m ) : NEW_LINE INDENT q . append ( [ ni , nj , t ] ) NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT matrix = [ [ 0 , 2 , 0 ] , [ 0 , 1 , 0 ] , [ 0 , 2 , 0 ] ] NEW_LINE if ( reachesBottom ( matrix ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT