Rat in a Maze Problem when movement in all possible directions is allowed | C ++ implementation of the above approach ; Function returns true if the move taken is valid else it will return false . ; Function to print all the possible paths from ( 0 , 0 ) to ( n - 1 , n - 1 ) . ; This will check the initial point ( i . e . ( 0 , 0 ) ) to start the paths . ; If reach the last cell ( n - 1 , n - 1 ) then store the path and return ; Mark the cell as visited ; Check if downward move is valid ; Check if the left move is valid ; Check if the right move is valid ; Check if the upper move is valid ; Mark the cell as unvisited for other possible paths ; Function to store and print all the valid paths ; vector to store all the possible paths ; Call the utility function to find the valid paths ; Print all possible paths ; Driver code
#include <bits/stdc++.h> NEW_LINE #define MAX  5 NEW_LINE using namespace std ; bool isSafe ( int row , int col , int m [ ] [ MAX ] , int n , bool visited [ ] [ MAX ] ) { if ( row == -1 row == n col == -1 col == n visited [ row ] [ col ] m [ row ] [ col ] == 0 ) return false ; return true ; } void printPathUtil ( int row , int col , int m [ ] [ MAX ] , int n , string & path , vector < string > & possiblePaths , bool visited [ ] [ MAX ] ) { if ( row == -1 row == n col == -1 col == n visited [ row ] [ col ] m [ row ] [ col ] == 0 ) return ; if ( row == n - 1 && col == n - 1 ) { possiblePaths . push_back ( path ) ; return ; } visited [ row ] [ col ] = true ; if ( isSafe ( row + 1 , col , m , n , visited ) ) { path . push_back ( ' D ' ) ; printPathUtil ( row + 1 , col , m , n , path , possiblePaths , visited ) ; path . pop_back ( ) ; } if ( isSafe ( row , col - 1 , m , n , visited ) ) { path . push_back ( ' L ' ) ; printPathUtil ( row , col - 1 , m , n , path , possiblePaths , visited ) ; path . pop_back ( ) ; } if ( isSafe ( row , col + 1 , m , n , visited ) ) { path . push_back ( ' R ' ) ; printPathUtil ( row , col + 1 , m , n , path , possiblePaths , visited ) ; path . pop_back ( ) ; } if ( isSafe ( row - 1 , col , m , n , visited ) ) { path . push_back ( ' U ' ) ; printPathUtil ( row - 1 , col , m , n , path , possiblePaths , visited ) ; path . pop_back ( ) ; } visited [ row ] [ col ] = false ; } void printPath ( int m [ MAX ] [ MAX ] , int n ) { vector < string > possiblePaths ; string path ; bool visited [ n ] [ MAX ] ; memset ( visited , false , sizeof ( visited ) ) ; printPathUtil ( 0 , 0 , m , n , path , possiblePaths , visited ) ; for ( int i = 0 ; i < possiblePaths . size ( ) ; i ++ ) cout << possiblePaths [ i ] << " ▁ " ; } int main ( ) { int m [ MAX ] [ MAX ] = { { 1 , 0 , 0 , 0 , 0 } , { 1 , 1 , 1 , 1 , 1 } , { 1 , 1 , 1 , 0 , 1 } , { 0 , 0 , 0 , 0 , 1 } , { 0 , 0 , 0 , 0 , 1 } } ; int n = sizeof ( m ) / sizeof ( m [ 0 ] ) ; printPath ( m , n ) ; return 0 ; }