5 solutions
-
0
Guest MOD
-
0
#include #include using namespace std;
// 偏移量:上、右、下、左 const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; // 每个方向下一步能转的方向(90度) const int next_dir[4][2] = {{1,3}, {0,2}, {1,3}, {0,2}};
// dp[k][x][y][d]:k步,坐标(x,y),方向d // 坐标偏移1000,避免负数(n最大1000,坐标范围-1000~1000) bool dp[1005][2005][2005][4]; int n;
int main() { cin >> n;
// 初始化:0步在原点,4个方向都合法 for (int d = 0; d < 4; d++) { dp[0][1000][1000][d] = true; } // 动态规划转移 for (int k = 0; k < n; k++) { for (int x = 0; x <= 2000; x++) { for (int y = 0; y <= 2000; y++) { for (int d = 0; d < 4; d++) { if (dp[k][x][y][d]) { // 尝试两个旋转后的方向 for (int nd : next_dir[d]) { int nx = x + dx[nd]; int ny = y + dy[nd]; dp[k+1][nx][ny][nd] = true; } } } } } } // 统计答案:n步后所有可达坐标 int ans = 0; for (int x = 0; x <= 2000; x++) { for (int y = 0; y <= 2000; y++) { bool ok = false; for (int d = 0; d < 4; d++) { if (dp[n][x][y][d]) { ok = true; break; } } if (ok) ans++; } } cout << ans << endl; return 0;}
Information
- ID
- 1605
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- (None)
- # Submissions
- 95
- Accepted
- 20
- Uploaded By