Check for possible path in 2D matrix | PHP 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 ]
< ? php $ row = 5 ; $ col = 5 ; function isPath ( $ arr ) { global $ row , $ col ; $ arr [ 0 ] [ 0 ] = 1 ; for ( $ i = 1 ; $ i < $ row ; $ i ++ ) if ( $ arr [ $ i ] [ 0 ] != -1 ) $ arr [ $ i ] [ 0 ] = $ arr [ $ i - 1 ] [ 0 ] ; for ( $ j = 1 ; $ j < $ col ; $ j ++ ) if ( $ arr [ 0 ] [ $ j ] != -1 ) $ arr [ 0 ] [ $ j ] = $ arr [ 0 ] [ $ j - 1 ] ; for ( $ i = 1 ; $ i < $ row ; $ i ++ ) for ( $ j = 1 ; $ j < $ col ; $ j ++ ) if ( $ arr [ $ i ] [ $ j ] != -1 ) $ arr [ $ i ] [ $ j ] = max ( $ arr [ $ i ] [ $ j - 1 ] , $ arr [ $ i - 1 ] [ $ j ] ) ; return ( $ arr [ $ row - 1 ] [ $ col - 1 ] == 1 ) ; } $ arr = array ( array ( 0 , 0 , 0 , 1 , 0 ) , array ( -1 , 0 , 0 , -1 , -1 ) , array ( 0 , 0 , 0 , -1 , 0 ) , array ( -1 , 0 , -1 , 0 , -1 ) , array ( 0 , 0 , -1 , 0 , 0 ) ) ; if ( isPath ( $ arr ) ) echo " Yes " ; else echo " No " ; ? >