# Rat in a Maze Problem - I | Practice | GeeksforGeeks

Thu Oct 19 2023 17:49:03 GMT+0000 (Coordinated Universal Time)

Saved by @DxBros #backtracking #medium

```class Solution{
public:
void findPaths(int i, int j, vector<string>& paths ,string path, vector<vector<int>>& mat){
if(i == mat.size()-1 && j == mat.size()-1)
{
paths.push_back(path);
return;
}
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
char move[4] = {'R','D','L','U'};
mat[i][j] = 0;
for(int k = 0; k < 4; k++){
int x = i + dx[k], y = j+ dy[k];
if((x>=0 && x < mat.size() && y >= 0 && y < mat.size()) && mat[x][y] != 0){

path.push_back(move[k]);
findPaths(x, y, paths, path, mat);
path.pop_back();
}
}
mat[i][j] = 1;
}
vector<string> findPath(vector<vector<int>> &mat, int n) {
// Your code goes here
vector<string> paths;
string path;
if(mat[0][0] == 0)
return paths;
findPaths(0, 0, paths, path, mat);
// sort(paths.begin(), paths.end());
return paths;

}
};```
content_copyCOPY

https://practice.geeksforgeeks.org/problems/rat-in-a-maze-problem/1