【CSP】CSP-J 2024真题 | 地图探险 luogu-P11228 （相当于GESP四级左右水平）

CSP-J 2024真题- 地图探险，模拟方法，二位数组考点，适合GESP四级（三级可挑战,五级可热手）左右水平的考生练习（二级需要先了解字符串），难度⭐⭐☆☆☆，洛谷难度等级普及−。

P11228 [CSP-J 2024] 地图探险

题目要求

题目描述

小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂，为了防止迷路，他先派遣了一个机器人前去探路。

丛林的地图可以用一个 $n$ 行 $m$ 列的字符表来表示。我们将第 $i$ 行第 $j$ 列的位置的坐标记作 $(i, j)(1 \leq i \leq n$，$1 \leq j \leq m)$。如果这个位置的字符为 $\tt x$，即代表这个位置上有障碍，不可通过。反之，若这个位置的字符为 $\tt.$，即代表这个位置是一片空地，可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 $(x, y)(1 \leq x \leq n$，$1 \leq y \leq m)$ 刻画，它表示机器人处在地图上第 $x$ 行第 $y$ 列的位置。而朝向用一个 $0 \sim 3$ 的整数 $d$ 表示，其中 $d = 0$ 代表向东，$d = 1$ 代表向南，$d = 2$ 代表向西，$d = 3$ 代表向北。

初始时，机器人的位置为 $(x_0, y_0)$，朝向为 $d_0$。保证初始时机器人所在的位置为空地。接下来机器人将要进行 $k$ 次操作。每一步，机器人将按照如下的模式操作：

1. 假设机器人当前处在的位置为 $(x, y)$，朝向为 $d$。则它的方向上的下一步的位置 $(x^′, y^′)$ 定义如下：若 $d = 0$，则令 $(x^′, y^′) = (x, y + 1)$，若 $d = 1$，则令 $(x^′, y^′) = (x + 1, y)$，若 $d = 2$，则令 $(x^′, y^′) = (x, y - 1)$，若 $d = 3$，则令 $(x^′, y^′) = (x - 1, y)$。

2. 接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断 $(x^′, y^′)$ 是否满足 $1 \leq x^′ \leq n, 1 \leq y^′ \leq m$，且 $(x^′, y^′)$ 位置上是空地。如果条件成立，则机器人会向前走一步。它新的位置变为 $(x^′, y^′)$，且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令 $d^′ = (d + 1) \bmod 4$（即 $d + 1$ 除以 $4$ 的余数），且它所处的位置保持不变，但朝向由 $d$ 变为 $d^′$。

小 A 想要知道，在机器人执行完 $k$ 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个正整数 $n, m, k$。其中 $n, m$ 表示地图的行数和列数，$k$ 表示机器人执行操作的次数。

第二行包含两个正整数 $x_0, y_0$ 和一个非负整数 $d_0$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。保证字符串中只包含 $\tt{x}$ 和 $\tt{.}$ 两个字符。其中，第 $x$ 行的字符串的第 $y$ 个字符代表的位置为 $(x, y)$。这个位置是 $\tt{x}$ 即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。

输出格式

对于每组数据：输出一行包含一个正整数，表示地图上所有被机器人经过的位置（包括起始位置）的个数。

输入输出样例 #1

输入 #1

2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....

输出 #1

3
13

说明/提示

【样例 1 解释】

该样例包含两组数据。对第一组数据，机器人的状态以如下方式变化：

1. 初始时，机器人位于位置 $(1, 1)$，方向朝西（用数字 $2$ 代表）。
2. 第一步，机器人发现它下一步的位置 $(1, 0)$ 不在地图内，因此，它会执行“向右转”操作。此时，它的位置仍然为 $(1, 1)$，但方向朝北（用数字 $3$ 代表）。
3. 第二步，机器人发现它下一步的位置 $(0, 1)$ 不在地图内，因此，它仍然会执行“向右转”操作。此时，它的位置仍然为 $(1, 1)$，但方向朝东（用数字 $0$ 代表）。
4. 第三步，机器人发现它下一步的位置 $(1, 2)$ 在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为 $(1, 2)$，方向仍然朝东。
5. 第四步，机器人发现它下一步的位置 $(1, 3)$ 在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为 $(1, 3)$，方向仍然朝东。

因此，四步之后，机器人经过的位置有三个，分别为 $(1, 1),(1, 2),(1, 3)$。

对第二组数据，机器人依次执行的操作指令为：向东走到 $(1, 2)$，向东走到 $(1, 3)$，向东走到 $(1, 4)$，向东走到 $(1, 5)$，向右转，向南走到 $(2, 5)$，向南走到 $(3, 5)$，向南走到 $(4, 5)$，向南走到 $(5, 5)$，向右转，向西走到 $(5, 4)$，向西走到 $(5, 3)$，向西走到 $(5, 2)$，向右转，向北走到 $(4, 2)$，向右转，向右转，向南走到 $(5, 2)$，向右转，向右转。

【样例 2】

见选手目录下的 explore/explore2.in 与 explore/explore2.ans。

该样例满足第 $3\sim 4$ 个测试点的限制条件。

【样例 3】

见选手目录下的 explore/explore3.in 与 explore/explore3.ans。

该样例满足第 $5$ 个测试点的限制条件。

【样例 4】

见选手目录下的 explore/explore4.in 与 explore/explore4.ans。

该样例满足第 $6$ 个测试点的限制条件。

【样例 5】

见选手目录下的 explore/explore5.in 与 explore/explore5.ans。

该样例满足第 $8 \sim 10$ 个测试点的限制条件。

【数据范围】

对于所有测试数据，保证：$1 \leq T \leq 5$，$1 \leq n, m \leq 10^3$，$1 \leq k \leq 10^6$，$1 \leq x_0 \leq n$，$1 \leq y_0 \leq m$，$0 \leq d_0 \leq 3$，且机器人的起始位置为空地。

测试点编号	$n$	$m$	$k$	特殊性质
$1$	$=1$	$\leq 2$	$=1$	无
$2$	^	^	^	^
$3$	$\leq 10^2$	$\leq 10^2$	^	^
$4$	^	^	^	^
$5$	$=1$	$\leq 10^3$	$\leq 2\times 10^3$	地图上所有位置均为空地
$6$	^	^	^	无
$7$	$\leq 10^3$	^	$\leq 10^6$	地图上所有位置均为空地
$8$	^	^	^	无
$9$	^	^	^	^
$10$	^	^	^	^

注：^ 表示与同列前一行测试点性质相同。

---

题目分析

这是一个典型的 二维网格模拟 题目。我们需要严格按照题目给定的规则，模拟机器人每一步的行动。

1. 核心状态与规则

机器人有两个核心属性需要维护：

1. 位置：当前所在的行 x 和列 y。
2. 方向：当前面朝的方向 d（0东、1南、2西、3北）。

每一轮操作（共 $k$ 次）逻辑如下：

• 尝试移动：根据当前方向计算“下一步的位置” $(x’, y’)$。
• 判断决策：
  • 能走：如果 $(x’, y’)$ 在地图内 且 不是障碍物（是 .），则更新位置 $(x, y) = (x’, y’)$。
  • 不能走：否则，原地不动，向右转（方向 d 变为 (d + 1) % 4）。
• 去重统计：如果到达了一个新的位置，计数器加 1。

2. 实现难点与技巧

方向处理（关键）：

题目定义了 0, 1, 2, 3 分别代表 东、南、西、北。观察坐标变化：

• 0 (东): $(x, y+1)$
• 1 (南): $(x+1, y)$
• 2 (西): $(x, y-1)$
• 3 (北): $(x-1, y)$

推荐使用 方向数组 dx[], dy[] 来简化代码，避免写大量的 if-else 或 switch 语句（当然本文两种方法都提供了了示例代码）：

// 0:右, 1:下, 2:左, 3:上
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

// 尝试往当前 d 方向走一步后的新坐标
int nx = x + dx[d];
int ny = y + dy[d];

向右转的操作也非常简单，就是方向编号 $+1$，并对 4 取模：d = (d + 1) % 4;。

去重统计：

题目要求统计“经过的位置个数”。我们可以使用一个二维布尔数组 vis[N][M] 来记录。

• 初始时，ans = 1（起点算经过），并标记起点 vis[x0][y0] = true。
• 每当移动到新位置 $(nx, ny)$ 时，检查 !vis[nx][ny]。若未访问过，则 ans++ 并标记 vis[nx][ny] = true。

坐标系转换：

题目输入的是 1-based 坐标（$1 \dots n$），而 C++ 数组通常是 0-based（$0 \dots n-1$）。建议在读入后立即将 $(x_0, y_0)$ 减 1，后续全程使用 0-based 坐标，方便判断边界（即 $0 \le x < n$ 且 $0 \le y < m$）。

3. 复杂度分析

• 时间复杂度：共有 $T$ 组数据，每组数据读入地图 $O(NM)$，模拟 $k$ 步操作，每步操作 $O(1)$。总复杂度为 $O(T \times (NM + k))$。本题 $NM \le 10^6, k \le 10^6$，时间非常充裕。
• 空间复杂度：$O(NM)$ 用于存储地图和访问标记。

---

示例代码

方法一：直接模拟

#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>

// 全局变量，用于存储地图和访问标记
std::string s[1005];
int vis[1005][1005];

int main() {
    // 优化 I/O 效率
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;  // 读取数据组数
    while (T--) {
        int n, m, k;
        std::cin >> n >> m >> k;  // 读取地图行数、列数和操作次数
        int x, y, d;
        std::cin >> x >> y >> d;  // 读取起始坐标 (x, y) 和初始朝向 d

        // 读取地图内容
        for (int i = 0; i < n; i++) {
            std::cin >> s[i];
        }

        int ans = 1;    // 记录经过的去重位置数量，初始位置算 1 个
        int cur_d = d;  // 当前朝向
        // 将输入的 1-based 坐标转换为 0-based 坐标，方便数组访问
        int cur_x = x - 1;
        int cur_y = y - 1;

        // 标记起始位置为已访问
        vis[cur_x][cur_y] = 1;

        // 模拟 k 次操作
        while (k--) {
            switch (cur_d) {
                case 0:  // 朝向东 (East)
                    // 判断下一步位置 (x, y+1) 是否在地图内且为空地
                    if (cur_y + 1 < m && s[cur_x][cur_y + 1] == '.') {
                        // 如果该位置未被访问过，则增加计数并标记
                        if (vis[cur_x][cur_y + 1] == 0) {
                            vis[cur_x][cur_y + 1] = 1;
                            ans++;
                        }
                        cur_y++;  // 向东移动一步
                    } else {
                        cur_d = 1;  // 遇到障碍或出界，向右转（变为向南）
                    }
                    break;
                case 1:  // 朝向南 (South)
                    // 判断下一步位置 (x+1, y) 是否在地图内且为空地
                    if (cur_x + 1 < n && s[cur_x + 1][cur_y] == '.') {
                        if (vis[cur_x + 1][cur_y] == 0) {
                            vis[cur_x + 1][cur_y] = 1;
                            ans++;
                        }
                        cur_x++;  // 向南移动一步
                    } else {
                        cur_d = 2;  // 向右转（变为向西）
                    }
                    break;
                case 2:  // 朝向西 (West)
                    // 判断下一步位置 (x, y-1) 是否在地图内且为空地
                    if (cur_y - 1 >= 0 && s[cur_x][cur_y - 1] == '.') {
                        if (vis[cur_x][cur_y - 1] == 0) {
                            vis[cur_x][cur_y - 1] = 1;
                            ans++;
                        }
                        cur_y--;  // 向西移动一步
                    } else {
                        cur_d = 3;  // 向右转（变为向北）
                    }
                    break;
                case 3:  // 朝向北 (North)
                    // 判断下一步位置 (x-1, y) 是否在地图内且为空地
                    if (cur_x - 1 >= 0 && s[cur_x - 1][cur_y] == '.') {
                        if (vis[cur_x - 1][cur_y] == 0) {
                            vis[cur_x - 1][cur_y] = 1;
                            ans++;
                        }
                        cur_x--;  // 向北移动一步
                    } else {
                        cur_d = 0;  // 向右转（变为向东）
                    }
                    break;
            }
        }

        // 清空 visited 数组，为下一组数据做准备
        // 注意：这里使用的是全局 vis 数组，需要重置
        memset(vis, 0, sizeof(vis));

        std::cout << ans << std::endl;  // 输出结果
    }
    return 0;
}

方法二：使用方向数组 - 【推荐掌握】

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 定义方向数组：东、南、西、北
// d=0: 东 (x, y+1) -> dx=0, dy=1
// d=1: 南 (x+1, y) -> dx=1, dy=0
// d=2: 西 (x, y-1) -> dx=0, dy=-1
// d=3: 北 (x-1, y) -> dx=-1, dy=0
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;  // 读取地图大小和操作次数

    int x0, y0, d0;
    cin >> x0 >> y0 >> d0;  // 读取初始位置和朝向

    // 使用 vector 存储地图，方便管理内存
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    // 使用 vector<vector<bool>> 记录访问过的位置
    // 初始化为 false，大小为 n 行 m 列
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    // 将输入的 1-based 坐标转换为 0-based 坐标
    int x = x0 - 1;
    int y = y0 - 1;
    int d = d0;

    // 标记起始点为已访问
    visited[x][y] = true;
    int count = 1;  // 经过的位置数量，初始位置算 1 个

    // 模拟 k 步操作
    for (int i = 0; i < k; ++i) {
        // 计算按照当前方向 d 走一步后的新坐标
        int nx = x + dx[d];
        int ny = y + dy[d];

        // 检查新坐标是否在地图范围内，且是否是空地
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.') {
            // 如果满足条件，向前移动
            x = nx;
            y = ny;
            // 如果这个位置之前没来过，计数加 1，并标记为已访问
            if (!visited[x][y]) {
                visited[x][y] = true;
                count++;
            }
        } else {
            // 如果不满足条件（越界或有障碍），向右转
            // (d + 1) % 4 可以实现 0->1, 1->2, 2->3, 3->0 的循环
            d = (d + 1) % 4;
        }
    }

    cout << count << endl;
}

int main() {
    // 加速 C++ 标准流 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {  // 读取测试数据组数
        while (t--) {
            solve();
        }
    }

    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号