题解 P1126 【机器人搬重物】

· · 题解

一道bfs题，说一说实现细节吧。

  1. 首先要把图坐标转化为点坐标，如果这个点左上、左下、右上、右下有1，则机器人站不到该点，我用1表示站不上的点，0代表能站上。

  2. 然后是方向变换，下面用int变量d代表方向，0,1,2,3分别代表N,W,S,E，往左转的话就是(d+1)%4,往右转就是(d-1+4)%4。这样就省去了分为各种情况进行方向判断的麻烦操作。

  3. 最后是前进1~3步的情况，需要注意的是如果前进1步or2步到达的点越界或者该点值为1，则后面的点在当前步数一定到达不了，就不需要添加到队列了。需要区分的是如果1步or2步的点加上到达点后所在方向已经被访问过，则后面的点还需要考虑。

附上AC代码，可以注意下我对方向的处理。


#include <iostream>
#include <map>
#include <queue>

using namespace std;

struct robot {
    int r;
    int c;
    int d;//0 N 1 W 2 S 3 E
};

int N, M;
int arr[55][55];
int sr, sc;
int er, ec;
char sd;
int vec[55][55];
bool vis[55][55][4];
map<char, int> ma;
int d1[4] = { -1,0,1,0 };
int d2[4] = { 0,-1,0,1 };

void init() {
    ma['N'] = 0;
    ma['W'] = 1;
    ma['S'] = 2;
    ma['E'] = 3;
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            if (arr[i - 1][j - 1] == 1 || arr[i - 1][j] == 1 || arr[i][j - 1] == 1 || arr[i][j] == 1) {
                vec[i][j] = 1;
            }
            else {
                vec[i][j] = 0;
            }
        }
    }
}

int bfs() {
    queue<robot> q;
    robot rb = { sr, sc, ma[sd] };
    vis[sr][sc][ma[sd]] = true;
    q.push(rb);
    int sum = 0;
    while (!q.empty()) {
        int len = q.size();
        for (int i = 0; i < len; i++) {
            rb = q.front();
            q.pop();
            if (rb.r == er && rb.c == ec) {
                return sum;
            }
            int k = rb.d;
            for (int j = 1; j <= 3; j++) {
                int a = rb.r + d1[k] * j;
                int b = rb.c + d2[k] * j;
                if (a < 1 || a >= N || b < 1 || b >= M || vec[a][b] == 1) {
                    break;
                }
                if (vis[a][b][k]) {
                    continue;
                }
                robot rot = { a,b,k };
                vis[a][b][k] = true;
                q.push(rot);
            }
            int dr = (k - 1 + 4) % 4;
            if(!vis[rb.r][rb.c][dr]){
                vis[rb.r][rb.c][dr] = true;
                q.push({ rb.r,rb.c,dr });
            }
            dr = (k + 1) % 4;
            if (!vis[rb.r][rb.c][dr]) {
                vis[rb.r][rb.c][dr] = true;
                q.push({ rb.r,rb.c,dr });
            }
        }
        sum++;
    }
    return -1;
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> arr[i][j];
        }
    }
    cin >> sr >> sc >> er >> ec >> sd;
    init();
    cout << bfs();
    return 0;
}