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 ; set arr [ 0 ] [ 0 ] = 1 ; Mark reachable ( from top left ) nodes in first row and first column . ; Mark reachable nodes in remaining matrix . ; return yes if right bottom index is 1 ; 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 arr [ 0 ] [ 0 ] = 1 NEW_LINE for i in range ( 1 , row ) : NEW_LINE INDENT if ( arr [ i ] [ 0 ] != - 1 ) : NEW_LINE INDENT arr [ i ] [ 0 ] = arr [ i - 1 ] [ 0 ] NEW_LINE DEDENT DEDENT for j in range ( 1 , col ) : NEW_LINE INDENT if ( arr [ 0 ] [ j ] != - 1 ) : NEW_LINE INDENT arr [ 0 ] [ j ] = arr [ 0 ] [ j - 1 ] NEW_LINE DEDENT DEDENT for i in range ( 1 , row ) : NEW_LINE INDENT for j in range ( 1 , col ) : NEW_LINE INDENT if ( arr [ i ] [ j ] != - 1 ) : NEW_LINE INDENT arr [ i ] [ j ] = max ( arr [ i ] [ j - 1 ] , arr [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT return ( arr [ row - 1 ] [ col - 1 ] == 1 ) 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