Check for possible path in 2D matrix | Python3 program to find if there is path from top left to right bottom ; to find the path from top left to bottom right ; directions ; queue ; insert the top right corner . ; until queue is empty ; mark as visited ; destination is reached . ; check all four directions ; using the direction array ; not blocked and valid ; Given array ; path from arr [ 0 ] [ 0 ] to arr [ row ] [ col ]
row = 5 NEW_LINE col = 5 NEW_LINE def isPath ( arr ) : NEW_LINE INDENT Dir = [ [ 0 , 1 ] , [ 0 , - 1 ] , [ 1 , 0 ] , [ - 1 , 0 ] ] NEW_LINE q = [ ] NEW_LINE q . append ( ( 0 , 0 ) ) NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT p = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE arr [ p [ 0 ] ] [ p [ 1 ] ] = - 1 NEW_LINE if ( p == ( row - 1 , col - 1 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT for i in range ( 4 ) : NEW_LINE INDENT a = p [ 0 ] + Dir [ i ] [ 0 ] NEW_LINE b = p [ 1 ] + Dir [ i ] [ 1 ] NEW_LINE if ( a >= 0 and b >= 0 and a < row and b < col and arr [ a ] [ b ] != - 1 ) : NEW_LINE INDENT q . append ( ( a , b ) ) NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT arr = [ [ 0 , 0 , 0 , - 1 , 0 ] , [ - 1 , 0 , 0 , - 1 , - 1 ] , [ 0 , 0 , 0 , - 1 , 0 ] , [ - 1 , 0 , - 1 , 0 , - 1 ] , [ 0 , 0 , - 1 , 0 , 0 ] ] NEW_LINE if ( isPath ( arr ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT