151 DSA Problem journey

151 DSA Problem journey

Rat in a maze

Q24:Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and rat cannot move to it while value 1 at a cell in the matrix represents that rat can be travel through it.
Note: In a path, no cell can be visited more than one time. If the source cell is 0, the rat cannot move to any other cell

Example :

Input:
N = 4
m[][] = {{1, 0, 0, 0},
         {1, 1, 0, 1}, 
         {1, 1, 0, 0},
         {0, 1, 1, 1}}
Output:
DDRDRR DRDDRR
Explanation:
The rat can reach the destination at 
(3, 3) from (0, 0) by two paths - DRDDRR 
and DDRDRR, when printed in sorted order 
we get DDRDRR DRDDRR.
Solution:
class Solution{
    public:
    bool isSafe(int newx,int newy,vector<vector<bool>>& vis,
    vector<vector<int>>&arr int n){
        if((newx>=0 && newx<n) && (newy>=0 && newy<n) &&(vis[newx][newy]!=1)
            && (arr[newx][newy]==1)){
             return true;
            }
            else{
                return false;
}               }
     void solve(int x,int y,vector < vector < int >> & arr,
      int n,vector < string > &ans,
vector<vector<bool>> visited,string path){
        if(x==n-1 && y==n-1){
            ans.push_back(path);
            return ;
        }
        visited[x][y]=1;
        //downnward
        if(isSafe(x+1,y,visited,arr,n)){
            solve(x+1,y,arr,n,ans,visited,path+'D');
        }
         if(isSafe(x,y-1,visited,arr,n)){
            solve(x,y-1,arr,n,ans,visited,path+'L');
        }
        //right
        if(isSafe(x,y+1,visited,arr,n)){
            solve(x,y+1,arr,n,ans,visited,path+'R');
        }
        //left

        //upward
        if(isSafe(x-1,y,visited,arr,n)){
            solve(x-1,y,arr,n,ans,visited,path+'U');
        }    
        visited[x][y]=0;    
    }
    vector<string> findPath(vector<vector<int>> &m, int n) {    
        vector<string> ans;
       if(m[0][0]==0){
           return ans;
       }
       vector<vector<bool>> vis(n,vector<bool>(n,0));
       string path="";
       solve(0,0,m,n,ans,vis,path);
       return ans;  
    }
};
Explaination:
This C++ code solving a problem of finding a path in a maze represented 
by a binary matrix. The goal is to find all possible paths from the 
top-left corner (starting point) to the bottom-right corner (ending point). 
Let's break down the code:

>isSafe Function:
 This function checks if it's safe to move to a new position (newx, newy)
 on the matrix.
 Conditions for it to be safe:
 The new position is within the boundaries of the matrix (newx and newy 
 are greater than or equal to 0 and less than n).
 The new position is not visited (vis[newx][newy] is not equal to 1).
 The value at the new position in the matrix (arr[newx][newy]) is 1 
 (indicating a valid path).
 If all conditions are met, it returns true; otherwise, it returns false.

>solve Function:
 This function performs a depth-first search (DFS) to explore all possible 
 paths from the current position (x, y) to the bottom-right corner (n-1, n-1)
 in the matrix.
 It uses backtracking to explore different paths.
 If the current position is the bottom-right corner, it adds the current 
 path to the ans vector.
 It explores in four directions: downward ('D'), left ('L'), right ('R'),
 and upward ('U'), based on the isSafe function.
 The path parameter keeps track of the current path being explored.
 After exploring all possible paths from the current position, it marks
 the current position as not visited (visited[x][y] = 0).

>findPath Function:
 This is the main function that initiates the path-finding process.
 It initializes an empty vector of strings (ans) to store the paths.
 If the starting point (m[0][0]) is not accessible (value is 0), it returns 
 an empty vector.
 It creates a matrix (vis) to keep track of visited positions and initializes 
 a string (path) to store the current path.
 Calls the solve function to find all paths starting from the top-left corner.
 Returns the vector containing all valid paths.

>In summary, the code uses a depth-first search approach to explore and find 
all possible paths from the top-left corner to the bottom-right corner in a 
maze represented by a binary matrix. The paths are stored in a vector of 
strings (ans).

Did you find this article valuable?

Support GAURAV YADAV by becoming a sponsor. Any amount is appreciated!