青创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