Hi, I am trying to solve Grid Paths from CSES (https://cses.fi/problemset/result/5369523/).

I got the correct answer but it's TLE. My solution uses ~10s. Any idea? Thank you.

string q;
bool visiting[7][7] = {false};
int cnt = 0;

void dfs(int i, int j, int walk) {
	if (i < 0 || i > 6 || j < 0 || j > 6 || walk > 48 || visiting[i][j]) {
		return;
	}
	if (i == 6 && j == 0) {
		if (walk == 48) {
			cnt++;
		}
		return;
	}

	visiting[i][j] = true;

	if (q[walk] == '?' || q[walk] == 'L') {
		dfs(i, j - 1, walk + 1);	
	}
	if (q[walk] == '?' || q[walk] == 'R') {
		dfs(i, j + 1, walk + 1);
	}
	if (q[walk] == '?' || q[walk] == 'U') {
		dfs(i - 1, j, walk + 1);
	}
	if (q[walk] == '?' || q[walk] == 'D') {
		dfs(i + 1, j, walk + 1);
	}
	
	visiting[i][j] = false;
}

void solve() {
	cin >> q;
	dfs(0, 0, 0);
	cout << cnt;
}