cpp/RATinMAZA.cpp at main · ksaini-web/cpp · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<vector>
using namespace std;

void helper(vector<vector<int>> mat,int r,int c,string path,vector<string>&ans){
//void helper(vector<vector<int>> mat,int r,int c,string path,vector<string>&ans,vector<vector<bool>>&vis){

int n=mat.size();


      if(r<0||c<0||r>=n||c>=n||mat[r][c]==0||mat[r][c]==-1){// if(r<0||c<0||r>=n||c>=n||mat[r][c]==0||vis[r][c]==true){
        return ;
    }
   if(r==n-1&&c==n-1){
    ans.push_back(path);
    return ;
   }
// vis[r][c]=true;
mat[r][c]=-1;
    //down
    helper(mat,r+1,c,path+"D",ans);//,vis
    //up
    helper(mat,r-1,c,path+"U",ans);//,vis
   //left
   helper(mat,r,c-1,path+"L",ans);//,vis
   //right
   helper(mat,r,c+1,path+"R",ans);//,vis
   mat[r][c]=1;
// vis[r][c]=false;

}


//complete this fuction

vector<string> Findpath(vector<vector<int>> &mat){
int n=mat.size();


vector<string>ans;
string path ="";
vector<vector<bool>>vis(n,vector<bool>(n,false));
helper(mat,0,0,path,ans);
return ans;
}

int main(){

    vector<vector<int>> mat ={{1,0,0,0},{1,1,0,1},{1,1,0,0},{0,1,1,1}};

    vector<string> ans=Findpath(mat);

    for(string path : ans){
        cout<<path<<endl;
    }

    return 0;
}