P1126 机器人搬重物 BFS广搜题解

原题链接：P1126 机器人搬重物

首先分析题目，题目要求求出最短时间，即为最短步骤，那么很明显应该采用广搜解决

首先第一个坑点：障碍物阻挡路径，我们在读入障碍物的时候需要将障碍物的四角点进行预处理，如图，一个障碍物阻挡四个点

解决了障碍物，接下来使方向问题，我们可以将方向数组特化处理，按照顺时针访问顺序排列，同时将反向转为数字表示，利用数字的递增关系实现顺时针旋转访问、前进，其余的与普通广搜基本一致，换向的代码需要额外注意。

AC Code

#include 
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 q;

int main(){
    cin >> n >> m;
    for(int i = 1; i  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 = m || sy