P1126 機器人搬重物 BFS廣搜題解

原題連結：​​P1126 機器人搬重物​​

首先分析題目，題目要求求出最短時間，即為最短步驟，那麼很明顯應該采用廣搜解決

首先第一個坑點：障礙物阻擋路徑，我們在讀入障礙物的時候需要将障礙物的四角點進行預處理，如圖，一個障礙物阻擋四個點

AC Code

#include <bits/stdc++.h>
using namespace std;
typedef struct robot{int x, y, dir, step;}robot;
const int N = 60;
const int a[] = {0, 1, 0, -1};
const int b[] = {1, 0, -1, 0};
int n, m, ans, g[N][N], vis[N][N][4];
int sx, sy, sf, tx, ty;
char sfc;
queue<robot> q;

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            cin >> g[i][j];
            if(g[i][j] == 1) g[i - 1][j] = g[i][j - 1] = g[i - 1][j - 1] = 1;
        }
    cin >> sx >> sy >> tx >> ty >> sfc;
    switch(sfc){
        default: break;
        case 'E': sf = 0; break;
        case 'S': sf = 1; break;
        case 'W': sf = 2; break;
        case 'N': sf = 3; break;
    }
    if(sx >= n || sx < 1 || sy >= m || sy < 1){
        cout << -1 << endl; return 0;
    }
    q.push(robot{sx, sy, sf, 0});
    vis[sx][sy][sf] = true;
    while(!q.empty()){
        robot tmp = q.front();
        q.pop();
        int nowx = tmp.x, nowy = tmp.y, nowf = tmp.dir;
        if(nowx == tx && nowy == ty){
            cout << tmp.step << endl;
            return 0;
        }
        for(int i = 1; i < 4; i++){
            nowx += a[nowf], nowy += b[nowf];
            if(nowx < 1 || nowx >= n || nowy < 1 || nowy >= m || g[nowx][nowy]) break;
            else if(!vis[nowx][nowy][nowf]){
                vis[nowx][nowy][nowf] = true;
                q.push(robot{nowx, nowy, nowf, tmp.step + 1});
            }
        }
             //轉向
        robot cnew{tmp.x, tmp.y, tmp.dir - 1,tmp.step + 1};
        if(cnew.dir == -1) cnew.dir = 3;
        if(!vis[cnew.x][cnew.y][cnew.dir]){vis[cnew.x][cnew.y][cnew.dir] = true; q.push(cnew);}
        cnew.dir = tmp .dir + 1;
        if(cnew.dir == 4) cnew.dir = 0; 
        if(!vis[cnew.x][cnew.y][cnew.dir]){vis[cnew.x][cnew.y][cnew.dir]=true; q.push(cnew);}
    }
    cout << -1 << endl;
    return 0;
}