5 solutions

  • 0
    @ 2026-4-8 18:11:31

    #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