2024 地图探险 · 方案一四方向分支写

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1614 字

按朝向分四支各自算目标格子

2024
模拟

正文

// CSP-J 2024 复赛 T2 · 地图探险
// 原题：https://oj.yecheng.tv/p/ccf-CSPJ2024B
// 题意：n 行 m 列的地图，x 是障碍、. 是空地。机器人有位置和朝向（0 东 1 南 2 西 3 北）。
// 每一步：先看朝向前一格在不在地图内、是不是空地 —— 是就走过去，不是就原地右转 90 度。
// 问 k 步之后一共走过多少个不同的位置（起点也算）。
//
// 方案一 · 用 if / else 把四个方向分别写出来
// 最直白的写法：按 d 的值分成四支，各自算出目标格子的坐标。
// 好处是读起来和题目描述一模一样，不容易把方向搞混。
// k 最大 1e6，一步一步模拟正好 O(k)，完全来得及。

#include <bits/stdc++.h>
using namespace std;

char mp[1005][1005];
bool vis[1005][1005];

int main() {
    freopen("explore.in", "r", stdin);
    freopen("explore.out", "w", stdout);

    int T;
    cin >> T;
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        int x, y, d;
        cin >> x >> y >> d;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> mp[i][j];
                vis[i][j] = false;
            }
        }

        vis[x][y] = true;
        int ans = 1;
        for (int step = 0; step < k; step++) {
            int nx = x, ny = y;
            if (d == 0) ny = y + 1;            // 东
            else if (d == 1) nx = x + 1;       // 南
            else if (d == 2) ny = y - 1;       // 西
            else nx = x - 1;                   // 北

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == '.') {
                x = nx;
                y = ny;                        // 走得通就走，朝向不变
                if (!vis[x][y]) {
                    vis[x][y] = true;
                    ans++;
                }
            } else {
                d = (d + 1) % 4;               // 走不通就原地右转
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

2024 地图探险 · 方案一 四方向分支写

正文

CSP-J 标程 · 复赛真题的其它内容

2024 地图探险 · 方案一四方向分支写