CSES - Shared codeLink to this code:
https://cses.fi/paste/73c59d03aa36764e288065/
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long unsigned llu;
string path;
int di[] = {-1,0,1,0}, dj[] = {0,-1,0,1};
char dir[] = "ULDR";
vector<vector<bool>> visited(7, vector<bool>(7, false));
ll backtrack(int i, int j, int step) {
//cout << string(step, ' ') << step << ' ' << i << ' ' << j << '\n';
if (i == 6 && j == 0) {
if (step != 48) {
return 0;
}
return 1;
} else {
int l, k, l1, k1, l2, k2, l3, k3;
ll sum = 0;
for (int m = 0; m < 4; ++m) {
if (path[step] != '?' && dir[m] != path[step]) continue;
//cout << string(step, ' ') << '-' << path[step] << ' ' << dir[m] << ' ' << di[m] << ' ' << dj[m] << '\n';
l = i + di[m];
k = j + dj[m];
if (l < 0 || k < 0 || l > 6 || k > 6 || visited[l][k])
continue;
l1 = l + di[m];
k1 = k + dj[m];
// Hit wall or itself
if (l1 < 0 || k1 < 0 || l1 > 6 || k1 > 6 || visited[l1][k1]) {
// "left" of the head
l2 = l + di[(m+1) - 4* (m==3)];
k2 = k + dj[(m+1) - 4* (m==3)];
// "right" of the head
l3 = l + di[(m-1) + 4* (m==0)];
k3 = k + dj[(m-1) + 4* (m==0)];
// "left" is off bounds or is visited
if (!(l2 < 0 || k2 < 0 || l2 > 6 || k2 > 6 || visited[l2][k2]) &&
// "right" is off bounds or is visited
!(l3 < 0 || k3 < 0 || l3 > 6 || k3 > 6 || visited[l3][k3])) {
//cout << "P!\n";
continue;
}
}
visited[l][k] = true;
sum += backtrack(l, k, step+1);
visited[l][k] = false;
}
return sum;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
ll res;
cin >> path;
visited[0][0] = true;
res = backtrack(0,0,0);
cout << res << '\n';
return 0;
}