#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
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,
string path, vector<vector<int>> visited) {
// you have reached x,y here
// base case
if (x == n - 1 && y == n - 1) {
ans.push_back(path);
return;
}
visited[x][y] = 1;
// 4 choices D,L,R,U
// down
int newx = x + 1;
int newy = y;
if (isSafe(newx, newy, n, visited, m)) {
path.push_back('D');
solve(m, n, ans, newx, newy, path, visited);
path.pop_back();
}
// left
newx = x;
newy = y - 1;
if (isSafe(newx, newy, n, visited, m)) {
path.push_back('L');
solve(m, n, ans, newx, newy, path, visited);
path.pop_back();
}
// right
newx = x;
newy = y + 1;
if (isSafe(newx, newy, n, visited, m)) {
path.push_back('R');
solve(m, n, ans, newx, newy, path, visited);
path.pop_back();
}
// up
newx = x - 1;
newy = y;
if (isSafe(newx, newy, n, visited, m)) {
path.push_back('U');
solve(m, n, ans, newx, newy, path, visited);
path.pop_back();
}
visited[x][y] = 0;
}
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, path, visited);
sort(ans.begin(), ans.end());
return ans;
}
int main() {
int n = 4;
vector<vector<int>> m = {
{1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}};
vector<string> ans = findPath(m, n);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}