zppz's blog

By zppz, history, 14 months ago, In English

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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

You can read the cp handbook of CSES.

https://cses.fi/book/book.pdf#page62