Rat in a maze (GFG) copy
unknown
plain_text
3 years ago
2.1 kB
4
Indexable
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; } };
Editor is loading...