机器人搬重物

题目：https://www.luogu.com.cn/problem/P1126
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个 N×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动11步（Creep）；向前移动2步（Walk）；向前移动33 步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1 秒。请你计算一下机器人完成任务所需的最少时间。

输入格式
第一行为两个正整数N,M(N,M≤50)，下面NN行是储藏室的构造，00表示无障碍，11表示有障碍，数字之间用一个空格隔开。接着一行有44个整数和11个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。

输入输出样例
输入 #1
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
输出 #1
12

题解：这道题看似是BFS算法，实际是最短路径算法，到达的方向与最终的结果有关，所以要存下坐标，方向，再按照各个步骤去模拟，但这道题有许多细节。
1.机器人是在点上行走，而障碍物是一个格子（四个点）。
2.机器人是一个球体，所以不能越界（0<x<n,0<y<m）。
3.转后方向也要模拟，但是要2秒。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
queue<int> qx,qy,qz;
int n,m,v[105][105][5],a[105][105],sx,sy,ex,ey,dx[5]={0,0,-1,0,1} ,dy[5]={0,1,0,-1,0} ;
int b[5][5]= {{0,0,0,0,0},{0,0,1,2,1},{0,1,0,1,2},{0,2,1,0,1},{0,1,2,1,0}} ;
char ch;

int bfs(int x,int y,int z)
{
    int f=0,t=1,cx,cy,cz,xx,yy,zz,i,j;
    v[x][y][z]=0;
    qx.push(x);
    qy.push(y);
    qz.push(z);
    while(!qx.empty())
    {
        cx=qx.front(),cy=qy.front(),cz=qz.front();
        qx.pop(),qy.pop(),qz.pop();
        for(i=1; i<=3; i++)
        {
            xx=dx[cz]*i+cx,yy=dy[cz]*i+cy;
            if(a[xx][yy]==1)
                break;
            if(xx>=1&&xx<n&&yy>=1&&yy<m&&v[cx][cy][cz]+1<v[xx][yy][cz])
            {
                v[xx][yy][cz]=v[cx][cy][cz]+1;
                qx.push(xx),qy.push(yy),qz.push(cz);
                t++;
            }
        }
        for(i=1; i<=4; i++)
        {
            if(cz==i)
                continue;

            if(v[cx][cy][i]>v[cx][cy][cz]+b[cz][i])
            {
                v[cx][cy][i]=v[cx][cy][cz]+b[cz][i];
                qx.push(cx),qy.push(cy),qz.push(i);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            cin>>a[i][j];
        }
    }
    cin>>sx>>sy>>ex>>ey>>ch;
    memset(v,127/3,sizeof(v));
    for(i=0; i<=n; i++)
        for(j=0; j<=m; j++)
            if(a[i+1][j]||a[i][j+1]||a[i+1][j+1])
                a[i][j]=1;
    if(ch=='E')
        ch='1';
    else if(ch=='N')
        ch='2';
    else if(ch=='W')
        ch='3';
    else
        ch='4';
    bfs(sx,sy,ch-'0');
//
    if(min(v[ex][ey][1],min(v[ex][ey][2],min(v[ex][ey][3],v[ex][ey][4])))>100000)
        cout<<-1<<endl;
    else
        cout<<min(v[ex][ey][1],min(v[ex][ey][2],min(v[ex][ey][3],v[ex][ey][4])))<<endl;
    return 0;
}