洛谷P1126 机器人搬重物

一道折磨了我整整一天的bfs

机器人搬重物

题目链接](https://www.luogu.org/problemnew/show/P1126)

• 这道题有一个坑点在于机器人是一个有体积的球走的是格点，所以可以一个障碍物在格点图上是四个障碍
• 还有就是转向的时间和向前走的时间是一样的，所以在bfs时它们是一层的。
  在一开始写的时候一不小心吧bfs写成了大特判调到现在也没调出来要是那个dalao比较闲可以帮帮LITTLESUN小菜鸡就实在是万分感谢啦！
  先把代码撂倒着啦！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAXN 2000
using namespace std;
int P[MAXN][MAXN];
int G[MAXN][MAXN];
int vis[MAXN][MAXN];
int tim[MAXN][MAXN];
int N,M;
int SX,SY,EX,EY;
char opt;
struct item 
{
    int x;
    int y;
    char op;
};
queue<item>q;
bool sign;
void bfs(item t)
{
    q.push(t);
    while(!q.empty())
    {
        item r;
        r=q.front();
        q.pop();
        //bool book=0;
        //if(vis[r.x][r.y]!=0) continue;
        if(r.op=='E')
        {
            if(tim[r.x][r.y+3]>=tim[r.x][r.y]+1&&G[r.x][r.y+3]==0&&r.y+3<=M)
            {
                //book=1;
                tim[r.x][r.y+3]=min(tim[r.x][r.y+3],tim[r.x][r.y]+1);
                vis[r.x][r.y+3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+3;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+2]>=tim[r.x][r.y]+1&&G[r.x][r.y+2]==0&&r.y+2<=M)
            {
                //book=1;
                tim[r.x][r.y+2]=min(tim[r.x][r.y+2],tim[r.x][r.y]+1);
                vis[r.x][r.y+2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+2;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+1]>=tim[r.x][r.y]+1&&G[r.x][r.y+1]==0&&r.y+1<=M)
            {
                //book=1;
                tim[r.x][r.y+1]=min(tim[r.x][r.y+1],tim[r.x][r.y]+1);
                vis[r.x][r.y+1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+1;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x+3][r.y]>=tim[r.x][r.y]+2&&G[r.x+3][r.y]==0&&r.x+3<=N)
            {
                //book=1;
                tim[r.x+3][r.y]=min(tim[r.x+3][r.y],tim[r.x][r.y]+2);
                vis[r.x+3][r.y]=1;
                item t2;
                t2.x=r.x+3;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+2][r.y]>=tim[r.x][r.y]+2&&G[r.x+2][r.y]==0&&r.x+2<=N )
            {
                //book=1;
                tim[r.x+2][r.y]=min(tim[r.x+2][r.y],tim[r.x][r.y]+2);
                vis[r.x+2][r.y]=1;
                item t2;
                t2.x=r.x+2;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+1][r.y]>=tim[r.x][r.y]+2&&G[r.x+1][r.y]==0&&r.x+1<=N )
            {
                //book=1;
                tim[r.x+1][r.y]=min(tim[r.x+1][r.y],tim[r.x][r.y]+2);
                vis[r.x+1][r.y]=1;
                item t2;
                t2.x=r.x+1;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x-3][r.y]>=tim[r.x][r.y]+2&&G[r.x-3][r.y]==0&&r.x-3>=0)
            {
                //book=1;
                tim[r.x-3][r.y]=min(tim[r.x-3][r.y],tim[r.x][r.y]+2);
                vis[r.x-3][r.y]=1;
                item t2;
                t2.x=r.x-3;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-2][r.y]>=tim[r.x][r.y]+2&&G[r.x-2][r.y]==0&&r.x-2>=0)
            {
                //book=1;
                tim[r.x-2][r.y]=min(tim[r.x-2][r.y],tim[r.x][r.y]+2);
                vis[r.x-2][r.y]=1;
                item t2;
                t2.x=r.x-2;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-1][r.y]>=tim[r.x][r.y]+2&&G[r.x-1][r.y]==0&&r.x-1>=0 )
            {
                //book=1;
                tim[r.x-1][r.y]=min(tim[r.x-1][r.y],tim[r.x][r.y]+2);
                vis[r.x-1][r.y]=1;
                item t2;
                t2.x=r.x-1;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x][r.y-3]>=tim[r.x][r.y]+3&&G[r.x][r.y-3]==0&&r.y-3>=0)
            {
                //book=1;
                tim[r.x][r.y-3]=min(tim[r.x][r.y-3],tim[r.x][r.y]+3);
                vis[r.x][r.y-3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-3;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-2]>=tim[r.x][r.y]+3&&G[r.x][r.y-2]==0&&r.y-2>=0)
            {
                //book=1;
                tim[r.x][r.y-2]=min(tim[r.x][r.y-2],tim[r.x][r.y]+3);
                vis[r.x][r.y-2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-2;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-1]>=tim[r.x][r.y]+3&&G[r.x][r.y-1]==0&&r.y-1>=0)
            {
                //book=1;
                tim[r.x][r.y-1]=min(tim[r.x][r.y-1],tim[r.x][r.y]+3);
                vis[r.x][r.y-1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-1;
                t2.op='W';
                q.push(t2);
            }
        }
        if(r.op=='W')
        {
            if(tim[r.x][r.y-3]>=tim[r.x][r.y]+1&&G[r.x][r.y-3]==0&&r.y-3>=0)
            {
                //book=1;
                tim[r.x][r.y-3]=min(tim[r.x][r.y-3],tim[r.x][r.y]+1);
                vis[r.x][r.y-3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-3;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-2]>=tim[r.x][r.y]+1&&G[r.x][r.y-2]==0&&r.y-2>=0)
            {
                //book=1;
                tim[r.x][r.y-2]=min(tim[r.x][r.y-2],tim[r.x][r.y]+1);
                vis[r.x][r.y-2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-2;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-1]>=tim[r.x][r.y]+1&&G[r.x][r.y-1]==0&&r.y-1>=0)
            {
                //book=1;
                tim[r.x][r.y-1]=min(tim[r.x][r.y-1],tim[r.x][r.y]+1);
                vis[r.x][r.y-1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-1;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x+3][r.y]>=tim[r.x][r.y]+2&&G[r.x+3][r.y]==0&&r.x+3<=N)
            {
                //book=1;
                tim[r.x+3][r.y]=min(tim[r.x+3][r.y],tim[r.x][r.y]+2);
                vis[r.x+3][r.y]=1;
                item t2;
                t2.x=r.x+3;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+2][r.y]>=tim[r.x][r.y]+2&&G[r.x+2][r.y]==0&&r.x+2<=N)
            {
                //book=1;
                tim[r.x+2][r.y]=min(tim[r.x+2][r.y],tim[r.x][r.y]+2);
                vis[r.x+2][r.y]=1;
                item t2;
                t2.x=r.x+2;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+1][r.y]>=tim[r.x][r.y]+2&&G[r.x+1][r.y]==0&&r.x+1<=N)
            {
                //book=1;
                tim[r.x+1][r.y]=min(tim[r.x+1][r.y],tim[r.x][r.y]+2);
                vis[r.x+1][r.y]=1;
                item t2;
                t2.x=r.x+1;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x-3][r.y]>=tim[r.x][r.y]+2&&G[r.x-3][r.y]==0&&r.x-3>=0)
            {
                //book=1;
                tim[r.x-3][r.y]=min(tim[r.x-3][r.y],tim[r.x][r.y]+2);
                vis[r.x-3][r.y]=1;
                item t2;
                t2.x=r.x-3;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-2][r.y]>=tim[r.x][r.y]+2&&G[r.x-2][r.y]==0&&r.x-2>=0)
            {
                //book=1;
                tim[r.x-2][r.y]=min(tim[r.x-2][r.y],tim[r.x][r.y]+2);
                vis[r.x-2][r.y]=1;
                item t2;
                t2.x=r.x-2;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-1][r.y]>=tim[r.x][r.y]+2&&G[r.x-1][r.y]==0&&r.x-1>=0)
            {
                //book=1;
                tim[r.x-1][r.y]=min(tim[r.x-1][r.y],tim[r.x][r.y]+2);
                vis[r.x-1][r.y]=1;
                item t2;
                t2.x=r.x-1;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x][r.y+3]>=tim[r.x][r.y]+3&&G[r.x][r.y+3]==0&&r.y+3<=M)
            {
                //book=1;
                tim[r.x][r.y+3]=min(tim[r.x][r.y+3],tim[r.x][r.y]+3);
                vis[r.x][r.y+3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+3;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+2]>=tim[r.x][r.y]+3&&G[r.x][r.y+2]==0&&r.y+2<=M)
            {
                //book=1;
                tim[r.x][r.y+2]=min(tim[r.x][r.y+2],tim[r.x][r.y]+3);
                vis[r.x][r.y+2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+2;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+1]>=tim[r.x][r.y]+3&&G[r.x][r.y+1]==0&&r.y+1<=M)
            {
                //book=1;
                tim[r.x][r.y+1]=min(tim[r.x][r.y+1],tim[r.x][r.y]+3);
                vis[r.x][r.y+1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+1;
                t2.op='E';
                q.push(t2);
            }
        }
        if(r.op=='S')
        {
            if(tim[r.x+3][r.y]>=tim[r.x][r.y]+1&&G[r.x+3][r.y]==0&&r.x+3<=N)
            {
                //book=1;
                tim[r.x+3][r.y]=min(tim[r.x+3][r.y],tim[r.x][r.y]+1);
                vis[r.x+3][r.y]=1;
                item t2;
                t2.x=r.x+3;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+2][r.y]>=tim[r.x][r.y]+1&&G[r.x+2][r.y]==0&&r.x+2<=N)
            {
                //book=1;
                tim[r.x+2][r.y]=min(tim[r.x+2][r.y],tim[r.x][r.y]+1);
                vis[r.x+2][r.y]=1;
                item t2;
                t2.x=r.x+2;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+1][r.y]>=tim[r.x][r.y]+1&&G[r.x+1][r.y]==0&&r.x+1<=N)
            {
                //book=1;
                tim[r.x+1][r.y]=min(tim[r.x+1][r.y],tim[r.x][r.y]+1);
                vis[r.x+1][r.y]=1;
                item t2;
                t2.x=r.x+1;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x][r.y-3]>=tim[r.x][r.y]+2&&G[r.x][r.y-3]==0&&r.y-3>=0)
            {
                //book=1;
                tim[r.x][r.y-3]=min(tim[r.x][r.y-3],tim[r.x][r.y]+2);
                vis[r.x][r.y-3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-3;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-2]>=tim[r.x][r.y]+2&&G[r.x][r.y-2]==0&&r.y-2>=0)
            {
                //book=1;
                tim[r.x][r.y-2]=min(tim[r.x][r.y-2],tim[r.x][r.y]+2);
                vis[r.x][r.y-2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-2;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-1]>=tim[r.x][r.y]+2&&G[r.x][r.y-1]==0&&r.y-1>=0)
            {
                //book=1;
                tim[r.x][r.y-1]=min(tim[r.x][r.y-1],tim[r.x][r.y]+2);
                vis[r.x][r.y-1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-1;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y+3]>=tim[r.x][r.y]+2&&G[r.x][r.y+3]==0&&r.y+3<=M)
            {
                //book=1;
                tim[r.x][r.y+3]=min(tim[r.x][r.y+3],tim[r.x][r.y]+2);
                vis[r.x][r.y+3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+3;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+2]>=tim[r.x][r.y]+2&&G[r.x][r.y+2]==0&&r.y+2<=M)
            {
                //book=1;
                tim[r.x][r.y+2]=min(tim[r.x][r.y+2],tim[r.x][r.y]+2);
                vis[r.x][r.y+2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+2;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+1]>=tim[r.x][r.y]+2&&G[r.x][r.y+1]==0&&r.y+1<=M)
            {
                //book=1;
                tim[r.x][r.y+1]=min(tim[r.x][r.y+1],tim[r.x][r.y]+2);
                vis[r.x][r.y+1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+1;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x-3][r.y]>=tim[r.x][r.y]+3&&G[r.x-3][r.y]==0&&r.x-3>=0)
            {
                //book=1;
                tim[r.x-3][r.y]=min(tim[r.x-3][r.y],tim[r.x][r.y]+3);
                vis[r.x-3][r.y]=1;
                item t2;
                t2.x=r.x-3;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-2][r.y]>=tim[r.x][r.y]+3&&G[r.x-2][r.y]==0&&r.x-2>=0)
            {
                //book=1;
                tim[r.x-2][r.y]=min(tim[r.x-2][r.y],tim[r.x][r.y]+3);
                vis[r.x-2][r.y]=1;
                item t2;
                t2.x=r.x-2;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-1][r.y]>=tim[r.x][r.y]+3&&G[r.x-1][r.y]==0&&r.x-1>=0)
            {
                //book=1;
                tim[r.x-1][r.y]=min(tim[r.x-1][r.y],tim[r.x][r.y]+3);
                vis[r.x-1][r.y]=1;
                item t2;
                t2.x=r.x-1;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            
        }
        if(r.op=='N')
        {
            if(tim[r.x-3][r.y]>=tim[r.x][r.y]+1&&G[r.x-3][r.y]==0&&r.x-3>=0)
            {
                //book=1;
                tim[r.x-3][r.y]=min(tim[r.x-3][r.y],tim[r.x][r.y]+1);
                vis[r.x-3][r.y]=1;
                item t2;
                t2.x=r.x-3;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-2][r.y]>=tim[r.x][r.y]+1&&G[r.x-2][r.y]==0&&r.x-2>=0)
            {
                //book=1;
                tim[r.x-2][r.y]=min(tim[r.x-2][r.y],tim[r.x][r.y]+1);
                vis[r.x-2][r.y]=1;
                item t2;
                t2.x=r.x-2;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x-1][r.y]>=tim[r.x][r.y]+1&&G[r.x-1][r.y]==0&&r.x-1>=0)
            {
                //book=1;
                tim[r.x-1][r.y]=min(tim[r.x-1][r.y],tim[r.x][r.y]+1);
                vis[r.x-1][r.y]=1;
                item t2;
                t2.x=r.x-1;
                t2.y=r.y;
                t2.op='N';
                q.push(t2);
            }
            if(tim[r.x][r.y-3]>=tim[r.x][r.y]+2&&G[r.x][r.y-3]==0&&r.y-3>=0)
            {
                //book=1;
                tim[r.x][r.y-3]=min(tim[r.x][r.y-3],tim[r.x][r.y]+2);
                vis[r.x][r.y-3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-3;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-2]>=tim[r.x][r.y]+2&&G[r.x][r.y-2]==0&&r.y-2>=0)
            {
                //book=1;
                tim[r.x][r.y-2]=min(tim[r.x][r.y-2],tim[r.x][r.y]+2);
                vis[r.x][r.y-2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-2;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y-1]>=tim[r.x][r.y]+2&&G[r.x][r.y-1]==0&&r.y-1>=0)
            {
                //book=1;
                tim[r.x][r.y-1]=min(tim[r.x][r.y-1],tim[r.x][r.y]+2);
                vis[r.x][r.y-1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y-1;
                t2.op='W';
                q.push(t2);
            }
            if(tim[r.x][r.y+3]>=tim[r.x][r.y]+2&&G[r.x][r.y+3]==0&&r.y+3<=M)
            {
                //book=1;
                tim[r.x][r.y+3]=min(tim[r.x][r.y+3],tim[r.x][r.y]+2);
                vis[r.x][r.y+3]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+3;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+2]>=tim[r.x][r.y]+2&&G[r.x][r.y+2]==0&&r.y+2<=M)
            {
                //book=1;
                tim[r.x][r.y+2]=min(tim[r.x][r.y+2],tim[r.x][r.y]+2);
                vis[r.x][r.y+2]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+2;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x][r.y+1]>=tim[r.x][r.y]+2&&G[r.x][r.y+1]==0&&r.y+1<=M)
            {
                //book=1;
                tim[r.x][r.y+1]=min(tim[r.x][r.y+1],tim[r.x][r.y]+2);
                vis[r.x][r.y+1]=1;
                item t2;
                t2.x=r.x;
                t2.y=r.y+1;
                t2.op='E';
                q.push(t2);
            }
            if(tim[r.x+3][r.y]>=tim[r.x][r.y]+3&&G[r.x+3][r.y]==0&&r.x+3<=N)
            {
                //book=1;
                tim[r.x+3][r.y]=min(tim[r.x+3][r.y],tim[r.x][r.y]+3);
                vis[r.x+3][r.y]=1;
                item t2;
                t2.x=r.x+3;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+2][r.y]>=tim[r.x][r.y]+3&&G[r.x+2][r.y]==0&&r.x+2<=N)
            {
                //book=1;
                tim[r.x+2][r.y]=min(tim[r.x+2][r.y],tim[r.x][r.y]+3);
                vis[r.x+2][r.y]=1;
                item t2;
                t2.x=r.x+2;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            if(tim[r.x+1][r.y]>=tim[r.x][r.y]+3&&G[r.x+1][r.y]==0&&r.x+1<=N)
            {
                //book=1;
                tim[r.x+1][r.y]=min(tim[r.x+1][r.y],tim[r.x][r.y]+3);
                vis[r.x+1][r.y]=1;
                item t2;
                t2.x=r.x+1;
                t2.y=r.y;
                t2.op='S';
                q.push(t2);
            }
            
        }
    }
    
}
int main()
{
    //freopen("ss.txt","r",stdin);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            scanf("%d",&P[i][j]);
        }
    }
    scanf("%d%d%d%d",&SX,&SY,&EX,&EY);
    scanf(" %c",&opt);
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M+1;j++)
        {
            G[i][j]=0;
        }
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(P[i][j]==1)
            {
                G[i][j]=1;
                G[i-1][j]=1;
                G[i][j-1]=1;
                G[i-1][j-1]=1;
            }
        }
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            tim[i][j]=2147483647;
            if(i==SX&&j==SY)
            {
                tim[i][j]=0;
            }
        }
    }
    item t;
    t.x=SX;
    t.y=SY;
    t.op=opt;
    bfs(t);
    for(int i=0;i<=N;i++)
    {
        for(int j=0;j<=M;j++)
        {
            printf("%d ",G[i][j]);
        }
        cout<<endl;
    }
    for(int i=0;i<=N;i++)
    {
        for(int j=0;j<=M;j++)
        {
            printf("%d ",tim[i][j]);
        }
        cout<<endl;
    }
    if(tim[EX][EY]!=2147483647)
    {
        printf("%d",tim[EX][EY]);
    }
    else
    {
        printf("-1");
    }
    return 0;
 } 

换了个思路之后的AC代码如下：

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>

using namespace std;
const int MAXN = 55;

int G[MAXN][MAXN];
int opt;
int vis[MAXN][MAXN][4];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int N,M;
int SX,SY,EX,EY;
char op;
int nx,ny;
struct item
{
    int x;
    int y;
    int f;
    int cnt;
};
queue<item>q;
bool ob(int x,int y)
{
    if(G[x][y]||G[x+1][y]||G[x][y+1]||G[x+1][y+1])
    {
        return 1;
    }
    return 0;
 } 
void bfs(item t)
{
    int x,y,f,cnt;
    q.push(t);
    while(!q.empty())
    {
        item r;
        r=q.front();
        q.pop();
        
         x=r.x;
         y=r.y;
         f=r.f;
         cnt=r.cnt;
        //printf( "x=%d y=%d f=%d cnt=%d\n", x, y, f, cnt );
        if(x==EX&&y==EY)
        {
            printf("%d",cnt);
            exit(0);
        }
        r.cnt++;
        r.f=(f+3)%4;
            if( vis[r.x][r.y][r.f] != 1 ) 
                q.push(r), vis[r.x][r.y][r.f] = 1;
        r.f=(f+5)%4;
            if( vis[r.x][r.y][r.f] != 1 ) 
                q.push(r), vis[r.x][r.y][r.f] = 1;
        r.f=f;
        for(int i=1;i<=3;i++)
        {
            nx=x+dx[f]*i;
            ny=y+dy[f]*i;
            if(nx<=0||nx>=N||ny<=0||ny>=M||ob(nx,ny)) break;
            r.x=nx;
            r.y=ny;
            if( vis[r.x][r.y][r.f] != 1 ) 
                q.push(r), vis[r.x][r.y][r.f] = 1;
        }
        
    }
}
int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            scanf("%d",&G[i][j]);
        }
    }
    scanf("%d%d%d%d",&SX,&SY,&EX,&EY);
    cin>>op;

    if(op=='N') opt=0;
    else if(op=='E') opt=1;
    else if(op=='S') opt=2;
    else if(op=='W') opt=3;
    item t;
    t.x=SX;
    t.y=SY;
    t.f=opt;
    t.cnt=0;
    bfs(t);
    printf("-1");
    return 0;
 } 

洛谷P1126 机器人搬重物

原文：https://www.cnblogs.com/LITTLESUNwl/p/10703358.html