lecture 40 code not available
Bro-SmisH opened this issue · 1 comments
Bro-SmisH commented
bhaiya rat in a maze wala code link nhi hai so please if possible give that
GarvonGit commented
bhaiya rat in a maze wala code link nhi hai so please if possible give that
class Solution{
private:
bool isSafe(int x, int y,int n, vector<vector> visited,vector<vector> &m){
//condition to be satisfied that next moment is safe or not
if((x>=0 && x<n) && (y>=0 && y<n) && visited[x][y]==0 && m[x][y]==1){
return true;
}
else{
return false;
}
}
void solve(vector<vector<int>> &m, int n,vector<string>&ans, int x,int y,
vector<vector<int>> visited, string path){
if(x==n-1 && y==n-1){
ans.push_back(path); //base case
return;
}
//if you are here then we can say, YOU ARE ON X,Y (0,0) WHICH HAS 1 IN BLOCK
visited[x][y]=1;
//4 choices - Down, Left, Right, Up
//DOWN
int newx = x+1;
int newy = y;
if(isSafe(newx,newy,n,visited,m)){
path.push_back('D');
solve(m,n,ans,newx,newy,visited,path);
path.pop_back();
}
//LEFT
newx = x;
newy = y-1;
if(isSafe(newx,newy,n,visited,m)){
path.push_back('L');
solve(m,n,ans,newx,newy,visited,path);
path.pop_back();
}
//RIGHT
newx = x;
newy = y+1;
if(isSafe(newx,newy,n,visited,m)){
path.push_back('R');
solve(m,n,ans,newx,newy,visited,path);
path.pop_back();
}
//UP
newx = x-1;
newy = y;
if(isSafe(newx,newy,n,visited,m)){
path.push_back('U');
solve(m,n,ans,newx,newy,visited,path);
path.pop_back();
}
visited[x][y]=0;
}
public:
vector<string> findPath(vector<vector<int>> &m, int n) {
vector<string>ans;
int srcx=0;
int srcy=0;
if(m[0][0]==0){
return ans;
}
vector<vector<int>>visited=m;
//initialized the visited matrix with 0
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
visited[i][j]=0;
}
string path="";
solve(m,n,ans,srcx,srcy,visited,path);
sort(ans.begin(),ans.end());
return ans;
}
}
};