Grid Paths

#include "bits/stdc++.h"
using namespace std;

string s;
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
int visitado[10][10];

int getDir(char c) {
    if(c == 'R')
        return 1;
    if(c == 'L')
        return 3;
    if(c == 'D')
        return 2;
    if(c == 'U')
        return 0;
    return -1;
}

int solve(int i, int r, int c) {
    if(i == s.size()) {
        if(r == 7 && c == 1)
            return 1;
        return 0;
    }

    // caso 1
    if(visitado[r][c - 1] == 1 && visitado[r][c + 1] == 1 &&
        visitado[r - 1][c] == 0 && visitado[r + 1][c] == 0)
        return 0;

    // caso 2
    if(visitado[r - 1][c] == 1 && visitado[r + 1][c] == 1 &&
        visitado[r][c - 1] == 0 && visitado[r][c + 1] == 0)
        return 0;

    //caso 3
    if(r == 7 && c == 1)
        return 0;

    int cnt = 0;
    int d = getDir(s[i]);

    visitado[r][c] = 1;

    if(d == -1) {
        for(int j = 0; j < 4; ++j) {
            if(visitado[ r + dr[j] ][ c + dc[j] ] == 0)
                cnt += solve(i + 1, r + dr[j], c + dc[j]);
        }
    } else if(visitado[ r + dr[d] ][ c + dc[d] ]  == 0) {
            cnt += solve(i + 1, r + dr[d], c + dc[d]);
    }

    visitado[r][c] = 0;

    return cnt;
}

int main() {
    cin >> s;

    for(int i = 0; i <= 8; ++i) {
        visitado[0][i] = 1;
        visitado[i][0] = 1;
        visitado[8][i] = 1;
        visitado[i][8] = 1;
    }

    cout << solve(0, 1, 1) << '\n';

    return 0;
}