P1126 机器人搬重物题解-526互联

Problem

题目概括

$n \times m $ 的网格，有些格子是障碍格。$0$ 无障碍，$1$ 有障碍。机器人有体积，总是在格点上。
有5种操作：
- 向前移动 $1/2/3$ 步
- 左转 $/$ 右转
每次操作需要 $1$ 秒。
求从 $x_1,y_1$ 到 $x_2,y_2$ 点的最短路。
机器人有一个初始方向 $ E / S / W / N$ (东南西北)。

思路

考察算法：BFS求最短路。
实现过程 $\&$ 注意点：
- 1. 障碍是在格子上的，需要将周围 $4$ 个点标记为障碍。
- 1. 本题下标从 $0$ 开始。
- 1. 由于机器人有体积，所以可走的范围只有 $(1,1) ～ (n - 1,m - 1)$ !
- 1. 在一次性走 $2,3$ 步的时候，一定要判断 $a$ 数组中路上的每一个点是否为 $0$。不然会出现 $“$ 穿墙 $”$ 的情况。

定义一个 queue<node> q; ，然后 $node$ 里面有 $4$ 个信息：$x,y,k,step$。 $k$ 代表当前的方向在方向数组中的下标，$step$ 表示花了几秒 $($走了几步$)$。

然后本题 $bool$ 类型的 $vis$ 数组可以开成三维的。
$vis[x][y][k]$ 代表 $x,y$ 点的 $k$ 方向已经被走过了。

然后 $BFS$ ，就可以 $AC$ 了～

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 60;
struct node {
    int X, Y, K, stp;
};
queue<node> q;
// 方向数组
int fx[5] = {0, 1, 0, -1};
int fy[5] = {1, 0, -1, 0};
int n, m;
int a[N][N], sx, sy, ex, ey, k, xx;
bool vis[N][N][5];
char c;
map<char, int> mp; // 映射四个方向对应方向数组的下标(0-3)

// 将障碍格四周的点标记为1
void fun(int x, int y) {
  a[x][y] = a[x - 1][y - 1] = a[x - 1][y] = a[x][y - 1] = 1;
}

// 检验坐标是否合法
bool check(int x, int y) { return x > 0 && x < n && y > 0 && y < m; }

// 左转
int TurnLeft(int tmpk) { return (tmpk + 3) % 4; }
// 右转
int TurnRight(int tmpk) { return (tmpk + 5) % 4; }

int bfs() {
    // 初始化
    q.push((node) {sx, sy, k, 0});
    vis[sx][sy][k] = true;
    while (!q.empty()) {
        int x = q.front().X, y = q.front().Y, tk = q.front().K, step = q.front().stp;
        q.pop();
        // 到达终点
        if (x == ex && y == ey) return step;
        // 左转 & 右转
        if (!vis[x][y][TurnLeft(tk)] && !a[x][y]) {
            q.push((node) {x, y, TurnLeft(tk), step + 1});
            vis[x][y][TurnLeft(tk)] = true;
        }
        if (!vis[x][y][TurnRight(tk)] && !a[x][y]) {
            q.push((node){x, y, TurnRight(tk), step + 1});
            vis[x][y][TurnRight(tk)] = true;
        }
        int oi = x + fx[tk], oj = y + fy[tk];
        int oi_2 = x + 2 * fx[tk], oj_2 = y + 2 * fy[tk];
        int oi_3 = x + 3 * fx[tk], oj_3 = y + 3 * fy[tk];
        // 走 1/2/3 步
        if (!vis[oi][oj][tk] && !a[oi][oj] && check(oi, oj)) {
            q.push((node){oi, oj, tk, step + 1});
            vis[oi][oj][tk] = true;
        }
        if (check(oi_2, oj_2) && !vis[oi_2][oj_2][tk] && !a[oi][oj] && !a[oi_2][oj_2]) {
            q.push((node){oi_2, oj_2, tk, step + 1});
            vis[oi_2][oj_2][tk] = true;
        }
        if (check(oi_3, oj_3) && !vis[oi_3][oj_3][tk] && !a[oi][oj] && !a[oi_2][oj_2] && !a[oi_3][oj_3]) {
            q.push((node){oi_3, oj_3, tk, step + 1});
            vis[oi_3][oj_3][tk] = true;
        }
    }
    return -1; // 走不到
}


int main() {
    mp['E'] = 0, mp['S'] = 1, mp['W'] = 2, mp['N'] = 3; // 初始化方向
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        a[i][0] = a[0][i] = a[i][m] = a[n][i] = 1;
        for (int j = 1; j <= m; j++) {
            scanf("%d", &xx);
            if (xx == 1) fun(i, j); // 障碍点四周的点都标记为1
        }
    }
    scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
    cin >> c;
    k = mp[c]; // 映射方向
    printf("%d", bfs());
    return 0;
}