[数据结构与算法]P1126 机器人搬重物（每日一题——搜索bfs）

机器人搬重物 🎁

🍋题解
这道题涉及到的细节问题相当多，我们需要注意机器人是有体积的，障碍物的周围机器人均不能通过；这道题的思路很重要，起初，我觉得这道题就是一个搜索加最短路维护一个数组，最终得到答案，但是在维护数组的过程中错误频频（改bug的痛苦）；但是呢，当我们再次仔细读题时，我们可以发现，我们完全可以将左转、右转、前进一二三步作为当前节点的下一步操作的子节点，然后一个bfs就可以轻松解决（当然了，我也考虑过，将转向作为一级结点，前进步数作为二级结点进行搜索，但是结果不尽人意，细节问题很难把握（菜是原罪啊））下面是AC的代码与一些必要的注释

🍓AC代码如下：

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

#define maxn 60
int vis[maxn][maxn][5]; //标记数组， 需要对位置、方向等状态进行标记
int map[maxn][maxn]; //地图数组，存图
const int my[4] = {0, 1, 0, -1};  //移动数组，特别注意的是，两个数组的移动方向，需要与下面对方向的标号相对应
const int mx[4] = {-1, 0, 1, 0};
int N, M, sx, sy, ex, ey; //定义必要的全局变量
char f;

//方向转化函数，对四个方向进行标号
int turn(char ch) {
    switch (ch) {
        case 'N':
            return 0;
        case 'E':
            return 1;
        case 'S':
            return 2;
        case 'W':
            return 3;
    }
}

//定义结构体
typedef struct node {
    int x, y; //位置坐标
    int dir; //方向
    int step; //步数
};

//对地图进行转化，将体积因素考虑进去
void change() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (map[i][j]) {
                map[i][j] = 1;
                map[i - 1][j] = 1;
                map[i - 1][j - 1] = 1;
                map[i][j - 1] = 1;
            }
        }
    }
}

//bfs搜索
void bfs(node start) {
    queue<node> q;
    q.push(start);
    while (!q.empty()) {
        node x = q.front();
        q.pop();
        if (x.x == ex && x.y == ey) { //设置出口
            cout << x.step;
            exit(0);
        }
        node next = x;
        if (vis[next.x][next.y][next.dir])  //因为子节点的状态比较多，在这里统一进行数组的标记
            continue;
        vis[next.x][next.y][next.dir] = 1;
        next.step++;

        next.dir = (x.dir + 4 - 1) % 4;  //左转
        q.push(next);

        next.dir = (x.dir + 4 + 1) % 4;  //右转
        q.push(next);

        next.dir = x.dir;  //恢复原来的方向，考虑前进的结点
        for (int i = 1; i <= 3; i++) {  //循环决定前进的步数
            next.x = x.x + i * mx[x.dir];
            next.y = x.y + i * my[x.dir];
            if (next.x <= 0 || next.y <= 0 || next.x >= N || next.y >= M || map[next.x][next.y])  //判断是否遇到障碍物
                break;
            q.push(next);
        }
    }
    cout << -1;
}

int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
        }
    }
    change();
    cin >> sx >> sy >> ex >> ey >> f;
    node start;
    start.x = sx, start.y = sy, start.dir = turn(f), start.step = 0;
    bfs(start);
}

虽然做题的时候走了很多弯路，最后写函数的时候也调试了很久，但是当完全解决这道题时，对广搜的理解会更深入😆，见多不怪。