forked from MukulCode/CodingClubIndia
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRatInAMaze.cpp
More file actions
33 lines (30 loc) · 1.03 KB
/
RatInAMaze.cpp
File metadata and controls
33 lines (30 loc) · 1.03 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Q59 https://practice.geeksforgeeks.org/problems/rat-in-a-maze-problem/1
// Time: 4(n*m)
// Space: O(m*n) Auxiliary space by the recursion tree
class Solution{
public:
void recf(int i, int j,vector<vector<int>> &m, int n, vector<string> &ans,string move,vector<vector<int>> &vis,int di[],int dj[]){
if(i==n-1&&j==n-1){
ans.push_back(move);
return;
}
string dir="DLRU";
for(int k=0;k<4;k++){
int ni=i+di[k];
int nj=j+dj[k];
if(ni>=0 && nj>=0 && ni<=n-1 && nj<=n-1 && !vis[ni][nj] && m[ni][nj]==1){
vis[i][j]=1;
recf(ni,nj,m,n,ans,move+dir[k],vis,di,dj);
vis[i][j]=0;
}
}
}
vector<string> findPath(vector<vector<int>> &m, int n) {
vector<string> ans;
vector<vector<int>> vis(n,vector<int>(n,0));
int di[]={1,0,0,-1}; //dlru
int dj[]={0,-1,1,0};
if(m[0][0]==1)recf(0, 0, m, n, ans,"", vis,di,dj);
return ans;
}
};