Check for possible path in 2D matrix | C ++ 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 ; Driver Code ; Given array ; path from arr [ 0 ] [ 0 ] to arr [ row ] [ col ]
#include <iostream> NEW_LINE using namespace std ; #define row  5 NEW_LINE #define col  5 NEW_LINE bool isPath ( int arr [ row ] [ col ] ) { arr [ 0 ] [ 0 ] = 1 ; for ( int i = 1 ; i < row ; i ++ ) if ( arr [ i ] [ 0 ] != -1 ) arr [ i ] [ 0 ] = arr [ i - 1 ] [ 0 ] ; for ( int j = 1 ; j < col ; j ++ ) if ( arr [ 0 ] [ j ] != -1 ) arr [ 0 ] [ j ] = arr [ 0 ] [ j - 1 ] ; for ( int i = 1 ; i < row ; i ++ ) for ( int 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 ) ; } int main ( ) { int arr [ row ] [ col ] = { { 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 } } ; if ( isPath ( arr ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }