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).