[CERC1996] 机器人搬重物

题意

给一个 N * M 的障碍网格。

机器人中心站在格点上，初始有一个朝向。每秒可以执行一条指令：

左转
右转
前进 1 步
前进 2 步
前进 3 步

要求求出从起点到终点的最少时间。如果无法到达，输出 -1。

思路

先看一个更直接的写法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int INF = 0x3f3f3f3f;

int n, m;
int obs[MAXN][MAXN];
int dist_arr[MAXN][MAXN][4];

int sx, sy, tx, ty;
string dir_name;

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

struct Node {
    int x, y, dir;
};

int get_dir_id(const string &s) {
    if (s == "E") return 0;
    if (s == "S") return 1;
    if (s == "W") return 2;
    return 3;
}

bool can_stand_here(int x, int y) {
    if (x < 1 || x >= n || y < 1 || y >= m) {
        return false;
    }

    // 直接现场检查四个相邻方格是否有障碍。
    if (obs[x][y] || obs[x - 1][y] || obs[x][y - 1] || obs[x - 1][y - 1]) {
        return false;
    }
    return true;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> obs[i][j];
        }
    }
    cin >> sx >> sy >> tx >> ty >> dir_name;

    if (!can_stand_here(sx, sy) || !can_stand_here(tx, ty)) {
        cout << -1 << '\n';
        return 0;
    }

    memset(dist_arr, 0x3f, sizeof(dist_arr));
    queue<Node> q;

    int start_dir = get_dir_id(dir_name);
    dist_arr[sx][sy][start_dir] = 0;
    q.push({sx, sy, start_dir});

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        int d = dist_arr[cur.x][cur.y][cur.dir];
        if (cur.x == tx && cur.y == ty) {
            cout << d << '\n';
            return 0;
        }

        int left_dir = (cur.dir + 3) % 4;
        if (dist_arr[cur.x][cur.y][left_dir] > d + 1) {
            dist_arr[cur.x][cur.y][left_dir] = d + 1;
            q.push({cur.x, cur.y, left_dir});
        }

        int right_dir = (cur.dir + 1) % 4;
        if (dist_arr[cur.x][cur.y][right_dir] > d + 1) {
            dist_arr[cur.x][cur.y][right_dir] = d + 1;
            q.push({cur.x, cur.y, right_dir});
        }

        for (int step = 1; step <= 3; step++) {
            int nx = cur.x + dx[cur.dir] * step;
            int ny = cur.y + dy[cur.dir] * step;
            if (!can_stand_here(nx, ny)) {
                break;
            }
            if (dist_arr[nx][ny][cur.dir] > d + 1) {
                dist_arr[nx][ny][cur.dir] = d + 1;
                q.push({nx, ny, cur.dir});
            }
        }
    }

    cout << -1 << '\n';
    return 0;
}

本题的核心有两个。

第一，状态不能只看坐标，还必须把朝向带上。

因为同一个位置，如果面朝不同方向，下一条“前进”指令到达的位置完全不同。

所以状态要写成：

text

1(x, y, dir)

第二，要先弄清楚“哪里不能站”。

题目给的是障碍格子，但机器人中心站在格点上，而且机器人直径大于 1。

因此某个格点只要周围四个小方格里有任意一个障碍，这个格点就不能站。

接下来就很自然了：

预处理每个格点是否可站
用 (x, y, dir) 作为状态做 BFS
每次扩展 5 种操作：
- 左转
- 右转
- 前进 1 步
- 前进 2 步
- 前进 3 步

因为每条指令代价都相同，BFS 第一次到达目标位置时就是最优答案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int INF = 0x3f3f3f3f;

int n, m;
int obs[MAXN][MAXN];          // 原始障碍格，按题目给出的 N*M 网格存
int can_stand[MAXN][MAXN];    // 机器人中心能否站在这个格点
int dist_arr[MAXN][MAXN][4];  // 最短路：位置 + 朝向

int sx, sy, tx, ty;
string dir_name;

// 方向顺序：东、南、西、北
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

struct Node {
    int x, y, dir;
};

int get_dir_id(const string &s) {
    if (s == "E") return 0;
    if (s == "S") return 1;
    if (s == "W") return 2;
    return 3; // N
}

bool inside_point(int x, int y) {
    // 机器人中心只能站在内部格点，边界上不行。
    return x >= 1 && x < n && y >= 1 && y < m;
}

void build_can_stand() {
    for (int x = 1; x < n; x++) {
        for (int y = 1; y < m; y++) {
            // 机器人直径大于 1，所以中心站在格点 (x,y) 时，
            // 周围四个小方格只要有一个是障碍，这个点就不能站。
            if (obs[x][y] || obs[x - 1][y] || obs[x][y - 1] || obs[x - 1][y - 1]) {
                can_stand[x][y] = 0;
            }
            else {
                can_stand[x][y] = 1;
            }
        }
    }
}

int bfs(int start_dir) {
    memset(dist_arr, 0x3f, sizeof(dist_arr));

    if (!inside_point(sx, sy) || !inside_point(tx, ty)) {
        return -1;
    }
    if (!can_stand[sx][sy] || !can_stand[tx][ty]) {
        return -1;
    }

    queue<Node> q;
    dist_arr[sx][sy][start_dir] = 0;
    q.push({sx, sy, start_dir});

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        int now_dist = dist_arr[cur.x][cur.y][cur.dir];
        if (cur.x == tx && cur.y == ty) {
            return now_dist;
        }

        // 左转
        int left_dir = (cur.dir + 3) % 4;
        if (dist_arr[cur.x][cur.y][left_dir] > now_dist + 1) {
            dist_arr[cur.x][cur.y][left_dir] = now_dist + 1;
            q.push({cur.x, cur.y, left_dir});
        }

        // 右转
        int right_dir = (cur.dir + 1) % 4;
        if (dist_arr[cur.x][cur.y][right_dir] > now_dist + 1) {
            dist_arr[cur.x][cur.y][right_dir] = now_dist + 1;
            q.push({cur.x, cur.y, right_dir});
        }

        // 向前走 1/2/3 步，每种指令代价都是 1。
        for (int step = 1; step <= 3; step++) {
            int nx = cur.x + dx[cur.dir] * step;
            int ny = cur.y + dy[cur.dir] * step;

            // 只要中途某一步撞到边界或障碍，后面更远的步数也都不能走了。
            if (!inside_point(nx, ny) || !can_stand[nx][ny]) {
                break;
            }

            if (dist_arr[nx][ny][cur.dir] > now_dist + 1) {
                dist_arr[nx][ny][cur.dir] = now_dist + 1;
                q.push({nx, ny, cur.dir});
            }
        }
    }

    return -1;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> obs[i][j];
        }
    }
    cin >> sx >> sy >> tx >> ty >> dir_name;

    build_can_stand();
    cout << bfs(get_dir_id(dir_name)) << '\n';

    return 0;
}

复杂度

时间复杂度： $O(N * M)$
空间复杂度： $O(N * M)$

总结

这题是很典型的“状态不只包含位置，还要包含方向”的 BFS。

真正容易写错的地方只有两个：

障碍判定针对的是格点，不是原始格子
前进 2/3 步时，中间经过的位置也必须全部合法

[CERC1996] 机器人搬重物

目录

题意

思路

代码

复杂度

总结