洛谷P1126机器人搬重物题解：C++广度优先搜索(BFS)实现与详细解析

一、题目解读

洛谷P1126是一道经典的搜索算法练习题，题目描述了一个2×2大小的机器人需要在网格地图中从起点移动到终点搬运重物。机器人可以进行三种操作：左转(耗时1分钟)、右转(耗时1分钟)或向前移动1-3步(每步耗时1分钟)。题目要求找出从起点到终点的最短时间。

二、解题思路

1. 状态表示：使用结构体Node记录机器人的坐标(x,y)、当前方向(dir)和已耗时(time)

2. 三维标记数组：vis[x][y][dir]记录特定位置和方向是否已被访问

3. 方向处理：将东南西北映射为0-3的数字，便于计算转向

4. 障碍检测：check函数验证机器人占用的4个格子是否都合法

5. BFS策略：每次扩展三种可能的操作(左转、右转、前进1-3步)

三、解题步骤

1. 初始化网格数据和起点终点信息

2. 将起点状态加入队列

3. 循环处理队列直到找到终点或队列为空：

• 检查是否到达终点

• 尝试左转和右转，生成新状态

• 尝试前进1-3步，遇到障碍则停止

4. 使用三维数组避免重复访问

5. 返回最短时间或-1(无法到达)

四、完整代码与注释

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int N = 55;
struct Node {
    int x, y, dir, time; // 坐标、方向、耗时
};

int n, m;
int grid[N][N];      // 原始网格
bool vis[N][N][4];   // 三维标记数组（坐标+方向）
// 方向数组：东南西北（对应题目给出的1-4）
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool check(int x, int y) {
    // 检查机器人占用的4个格子是否合法
    if (x < 1 || x >= n || y < 1 || y >= m) return false;
    return !(grid[x][y] || grid[x+1][y] || grid[x][y+1] || grid[x+1][y+1]);
}

int bfs(int sx, int sy, int sdir, int ex, int ey) {
    queue<Node> q;
    q.push({sx, sy, sdir, 0});
    vis[sx][sy][sdir] = true;

    while (!q.empty()) {
        Node cur = q.front(); q.pop();
        // 到达终点
        if (cur.x == ex && cur.y == ey) return cur.time;

        // 处理三种指令：左转、右转、前进
        for (int cmd = 0; cmd < 3; cmd++) {
            Node next = cur;
            if (cmd == 0) { // 左转
                next.dir = (cur.dir + 3) % 4;
            } else if (cmd == 1) { // 右转
                next.dir = (cur.dir + 1) % 4;
            } else { // 前进1-3步
                for (int step = 1; step <= 3; step++) {
                    next.x = cur.x + dx[cur.dir] * step;
                    next.y = cur.y + dy[cur.dir] * step;
                    if (!check(next.x, next.y)) break; // 遇到障碍停止
                    if (vis[next.x][next.y][next.dir]) continue;
                    vis[next.x][next.y][next.dir] = true;
                    next.time = cur.time + 1;
                    q.push(next);
                }
                continue;
            }
            if (!vis[next.x][next.y][next.dir]) {
                vis[next.x][next.y][next.dir] = true;
                next.time = cur.time + 1;
                q.push(next);
            }
        }
    }
    return -1; // 无法到达
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> grid[i][j];

    int sx, sy, ex, ey;
    char dir;
    cin >> sx >> sy >> ex >> ey >> dir;

    // 转换方向为数字标识
    int sdir;
    if (dir == 'E') sdir = 0;
    else if (dir == 'S') sdir = 1;
    else if (dir == 'W') sdir = 2;
    else sdir = 3;

    cout << bfs(sx, sy, sdir, ex, ey);
    return 0;
}

五、总结

本文详细解析了洛谷P1126题的BFS解法，通过三维状态表示和合理的剪枝策略高效解决了机器人路径规划问题。代码实现简洁明了，注释详细，适合算法学习者参考和实践。