Print all paths from a source point to all the 4 corners of a Matrix | C ++ program for the above approach ; Function to check if we reached on of the entry / exit ( corner ) point . ; Function to check if the index is within the matrix boundary . ; Recursive helper function ; If any corner is reached push the string t into ans and return ; For all the four directions ; The new ith index ; The new jth index ; The direction R / L / U / D ; If the new cell is within the matrix boundary and it is not previously visited in same path ; Mark the new cell as visited ; Store the direction ; Recur ; Backtrack to explore other paths ; Function to find all possible paths ; Create a direction array for all the four directions ; Stores the result ; Driver Code ; Initializing the variables ; Function Call ; Print the result
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct direction { int x , y ; char c ; } ; bool isCorner ( int i , int j , int M , int N ) { if ( ( i == 0 && j == 0 ) || ( i == 0 && j == N - 1 ) || ( i == M - 1 && j == N - 1 ) || ( i == M - 1 && j == 0 ) ) return true ; return false ; } bool isValid ( int i , int j , int M , int N ) { if ( i < 0 i > = M j < 0 j > = N ) return false ; return true ; } void solve ( int i , int j , int M , int N , direction dir [ ] , vector < vector < int > > & maze , string & t , vector < string > & ans ) { if ( isCorner ( i , j , M , N ) ) { ans . push_back ( t ) ; return ; } for ( int k = 0 ; k < 4 ; k ++ ) { int x = i + dir [ k ] . x ; int y = j + dir [ k ] . y ; char c = dir [ k ] . c ; if ( isValid ( x , y , M , N ) && maze [ x ] [ y ] == 1 ) { maze [ x ] [ y ] = 0 ; t . push_back ( c ) ; solve ( x , y , M , N , dir , maze , t , ans ) ; t . pop_back ( ) ; maze [ x ] [ y ] = 1 ; } } return ; } vector < string > possiblePaths ( vector < int > src , vector < vector < int > > & maze ) { direction dir [ 4 ] = { { -1 , 0 , ' U ' } , { 0 , 1 , ' R ' } , { 1 , 0 , ' D ' } , { 0 , -1 , ' L ' } } ; string temp ; vector < string > ans ; solve ( src [ 0 ] , src [ 1 ] , maze . size ( ) , maze [ 0 ] . size ( ) , dir , maze , temp , ans ) ; return ans ; } int main ( ) { vector < vector < int > > maze = { { 1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 } , { 1 , 1 , 1 , 0 , 0 , 0 , 1 , 0 } , { 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 } , { 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 } , { 1 , 0 , 1 , 0 , 1 , 0 , 0 , 1 } , { 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 } , { 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 } , { 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 } , } ; vector < int > src = { 4 , 2 } ; vector < string > paths = possiblePaths ( src , maze ) ; if ( paths . size ( ) == 0 ) { cout << " No ▁ Possible ▁ Paths " ; return 0 ; } for ( int i = 0 ; i < paths . size ( ) ; i ++ ) cout << paths [ i ] << endl ; return 0 ; }