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;
        
    }
};