PROBLEM:
MY SOLUTION:
vector findPath(vector<vector> &m, int n) {
vector<string> st;
string s;
solve(m, n, st, s, 0, 0, 'O');
return st;
}
void solve(vector<vector> &m, int n, vector &st, string &s, int i, int j, char prev) {
if (i == n || j == n || i == -1 || j == -1 || m[i][j] == 0) {
return;
}
if (i == n - 1 && j == n - 1) {
st.push_back(s);
return;
} else {
if (j + 1 < n && m[i][j + 1] == 1 && prev != 'L') {
s += 'R';
solve(m, n, st, s, i, j + 1, 'R');
s.pop_back();
}
if (i + 1 < n && m[i + 1][j] == 1 && prev != 'U') {
s += 'D';
solve(m, n, st, s, i + 1, j, 'D');
s.pop_back();
}
if (i - 1 >= 0 && m[i - 1][j] == 1 && prev != 'D') {
s += 'U';
solve(m, n, st, s, i - 1, j, 'U');
s.pop_back();
}
if (j - 1 >= 0 && m[i][j - 1] == 1 && prev != 'R') {
s += 'L';
solve(m, n, st, s, i, j - 1, 'L');
s.pop_back();
}
}
}