青创7基本功测试

Done IOI Start at: 2025-12-4 11:00 0.8 hour(s) Host: 31
#include <bits/stdc++.h>
using namespace std;
string s;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool vis[10][10];
int res;
void dfs(int now, int x, int y) {
	// 结束条件
	if ( now == 48) {
		if (x == 7 && y == 1)
			res++;
		return ;
	}
	// 剪枝,树,
	if (x == 7 && y == 1)
		return ;
	// 现在所处的位置是 x,y
	// 减枝
	if (x > 1 && x < 7 && y > 1 && y < 7 && vis[x - 1][y] && vis[x + 1][y] && !vis[x][y - 1] && !vis[x][y + 1])
		return ;
	if (x > 1 && x < 7 && y > 1 && y < 7 && !vis[x - 1][y] && !vis[x + 1][y] && vis[x][y - 1] && vis[x][y + 1])
		return ;
	if (x == 1 && y >= 2 && y <= 6 && !vis[x][y - 1] && !vis[x][y + 1])
		return ;
	if (x == 7 && y >= 2 && y <= 6 && !vis[x][y - 1] && !vis[x][y + 1])
		return ;
	if (y == 1 && x >= 2 && x <= 6 && !vis[x - 1][y] && !vis[x + 1][y])
		return ;
	if (y == 7 && x >= 2 && x <= 6 && !vis[x - 1][y] && !vis[x + 1][y])
		return ;
	// 没结束的情况呢????
	// s[now] 可能是 DULR ?
	if (s[now] == '?') {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > 7 || ny < 1 || ny > 7)
				continue;
			if (vis[nx][ny])
				continue;
			vis[nx][ny] = 1;
			dfs(now + 1, nx, ny);
			vis[nx][ny] = 0; // 回溯
		}
	} else {
		int nx, ny;
		if (s[now] == 'D')
			nx = x + 1, ny = y;
		if (s[now] == 'U')
			nx = x - 1, ny = y;
		if (s[now] == 'L')
			nx = x, ny = y - 1;
		if (s[now] == 'R')
			nx = x, ny = y + 1;
		if (nx < 1 || nx > 7 || ny < 1 || ny > 7)
			return ;
		if (vis[nx][ny])
			return ;
		vis[nx][ny] = 1;
		dfs(now + 1, nx, ny);
		vis[nx][ny] = 0; // 回溯
	}
}

int main() {
	cin >> s;
	vis[1][1] = 1;
	// dfs(字符串的位置,x的位置,y的位置)
	dfs(0, 1, 1);
	cout << res;
	return 0;
}
Status
Done
Rule
IOI
Problem
4
Start at
2025-12-4 11:00
End at
2025-12-4 11:45
Duration
0.8 hour(s)
Host
Partic.
31