Rat in a maze (GFG) copy

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.1 kB
2
Indexable
Never
class Solution
{
    
    private:
    
    bool isSafe(int x, int y, int n, vector<vector<int>> visited, vector<vector<int>>&m)
    {
        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);
            return;
        }
        visited [x][y]= 1;
        
        //down
        int newx = x+1;
        int newy=  y;
        if(isSafe(newx, newy, n, visited, m))
        {
            path.push_back('D');
            solve(m,n,newx,newy,visited, path);
            path.pop_back();
        }
        
         //left
         newx = x;
         newy=  y-1;
        if(isSafe(newx, newy, n, visisted, m)
        {
            path.push_back('L');
            solve(m,n,newx,newy,visited, path);
            path.pop_back();
        }
        
         //right
         newx = x;
         newy=  y+1;
        if(isSafe(newx, newy, n, visisted, m)
        {
            path.push_back('R');
            solve(m,n,newx,newy,visited, path);
            path.pop_back();
        }
        
         //up
         newx = x-1;
         newy=  y;
        if(isSafe(newx, newy, n, visisted, m)
        {
            path.push_back('U');
            solve(m,n,newx,newy,visited, path);
            path.pop_back();
        }
        
    }
    public:
    vector<string> findPath(vector<vector<int>> &m, int n) {
        vector<string>ans;
        
        if(m[0][0]==0)return ans;
        int srcx = 0;
        int srcy = 0;
        vector<vector<int>>visited = m;
        
        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;
    }
};