Shared code

#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;
 
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, const string &path) {
    //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, path);
            visited[l][k] = false;
        }
        return sum;
    }
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    ll res;
    
    string path;
    cin >> path;
 
    visited[0][0] = true;
    res = backtrack(0,0,0, path);
    
    cout << res << '\n';
    
    return 0;
}