[CSP-J 2024] 地图探险

GitHub跳转原题关系图返回列表

按照机器人规则模拟 k 步，用 visited 记录经过过的格子并统计不同位置数量。

OJ: luogu

题目 ID: P11228

难度:普及-

标签:模拟网格

日期: 2026-07-05 21:24

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定一个 n×mn \times m 的地图，. 表示空地，xx 表示障碍。机器人有当前位置 (x,y)(x, y) 和朝向 dd。

机器人执行 kk 次操作：

  • 如果前方一格在地图内且是空地，就向前走一步；
  • 否则原地右转，朝向变成 (d+1) mod 4(d + 1) \bmod 4。

问执行完 kk 步后，机器人一共经过了多少个不同的格子，起点也算经过。

思路

先看一个可以直接验证想法的朴素解：

cpp
// brute.cpp：小数据暴力解，严格按题意逐步模拟机器人的动作。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m, k;
int x, y, d;
char grid_map[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool can_go(int nx, int ny) {
    return 1 <= nx && nx <= n && 1 <= ny && ny <= m && grid_map[nx][ny] == '.';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        cin >> x >> y >> d;
        for (int i = 1; i <= n; i++) {
            string row;
            cin >> row;
            for (int j = 1; j <= m; j++) {
                grid_map[i][j] = row[j - 1];
                visited[i][j] = false;
            }
        }

        int answer = 1;
        visited[x][y] = true;

        for (int step = 1; step <= k; step++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (can_go(nx, ny)) {
                x = nx;
                y = ny;
                if (!visited[x][y]) {
                    visited[x][y] = true;
                    answer++;
                }
            } else {
                d = (d + 1) % 4;
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

这题的数据范围是 k<=106k <= 10^6，T<=5T <= 5，所以直接逐步模拟最多约 5×1065 × 10^6 次操作，可以通过。

实现时维护三个东西：

  1. 当前位置 (x,y)(x, y)；
  2. 当前朝向 dd；
  3. visited[i][j]visited[i][j] 表示格子 (i,j)(i,j) 是否已经经过。

每一步先根据朝向算出下一格：

d 方向 变化
00 东 (x,y+1)(x, y+1)
11 南 (x+1,y)(x+1, y)
22 西 (x,y−1)(x, y-1)
33 北 (x−1,y)(x-1, y)

如果下一格能走，就更新位置，并在第一次到达这个格子时让答案加一。 如果下一格不能走，只更新朝向，不改变位置，也不会增加经过格子数量。

代码

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

const int MAXN = 1005;

int n, m, k;
int x, y, d;
char grid_map[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool can_go(int nx, int ny) {
    return 1 <= nx && nx <= n && 1 <= ny && ny <= m && grid_map[nx][ny] == '.';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        cin >> x >> y >> d;
        for (int i = 1; i <= n; i++) {
            string row;
            cin >> row;
            for (int j = 1; j <= m; j++) {
                grid_map[i][j] = row[j - 1];
                visited[i][j] = false;
            }
        }

        int answer = 1;
        visited[x][y] = true;

        for (int step = 1; step <= k; step++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (can_go(nx, ny)) {
                x = nx;
                y = ny;
                if (!visited[x][y]) {
                    visited[x][y] = true;
                    answer++;
                }
            } else {
                d = (d + 1) % 4;
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

复杂度

  • 时间复杂度：O(Tk+Tnm)O(Tk + Tnm)
  • 空间复杂度：O(nm)O(nm)

总结

本题的核心是忠实模拟规则。右转时位置不变，只有真正走到一个新格子时，经过格子数才增加。