当前位置：首页 > 洛谷 > 洛谷P1126机器人移动问题：基于BFS算法的解题方案与代码

洛谷P1126机器人移动问题：基于BFS算法的解题方案与代码

5个月前 (07-22)

一、题目解读

洛谷P1126题要求解决一个机器人移动问题：在一个n×m的网格中，机器人占用相邻的4个格子，初始位置和方向已知，需通过左转、右转、前进1-3步的指令到达终点。题目需判断是否存在路径，并输出最短时间。关键点在于机器人移动时的位置合法性判断及指令组合。

二、解题思路

采用广度优先搜索（BFS）算法。核心思想：从起点开始，遍历所有可能的指令组合（左转、右转、前进），记录每个状态（坐标+方向+时间），利用三维标记数组避免重复搜索。方向数组简化移动计算，check函数验证机器人占用格子是否合法，确保每一步的有效性。

三、解题步骤

1. 输入处理：读取网格尺寸n×m及起点、终点坐标和方向。

2. BFS初始化：将起点状态（坐标、方向、时间0）入队，标记已访问。

3. 指令处理循环：

○ 左转/右转：更新方向，标记新状态并入队。

○ 前进1-3步：逐步扩展，若遇到障碍或超出边界停止；合法则标记并更新时间。

4. 终止条件：到达终点时返回时间，否则无法到达返回-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;
}