bfs的一些题

P1126 机器人搬重物
题意：给起点 将机器人移动到 终点
可以进行的操作：前进1步，前进2步，前进3步，左转，右转 花费1时间
分析：使用bfs寻找最小时间，但是这题有一些坑

1. 首先机器人有体积，所以机器人的中心不能落在最外围
2. 起点 终点 周围不能有墙，否则到达不了
3. 进行前进操作 要判断过程中有没有墙，不然会有穿墙操作
4. 状态标记 三维标记 位置（x,y)和方向

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int N = 55;
int n,m;
int x1,x2,y1,y2;
char fang;
int a[N][N];
bool vis[N][N][N];

struct Node{
    int x,y;
    int fang;//E W N S
    int time;
}t;

int dd[3]={1,2,3};


int bfs(Node u)
{
    queue<Node>q;
    q.push(u);
    vis[x1][y1][u.fang]=1;
    //起点 终点 是否不可到达
    if(a[x2][y2]==1||a[x2][y2]==1||a[x2][y2]==1||a[x2][y2]==1)return -1;
    if(a[x1][y1]==1||a[x1][y1]==1||a[x1][y1]==1||a[x1][y1]==1)return -1;
    while(q.size())
    {
        t=q.front();
        q.pop();

        if(t.x==x2&&t.y==y2)
            return t.time;
        for(int i=0;i<3;i++)
        {
            //按照方向 走1-3步
            int xx=t.x,yy=t.y;
            if(t.fang==1)yy+=dd[i];
            else if(t.fang==2)yy-=dd[i];
            else if(t.fang==3)xx-=dd[i];
            else xx+=dd[i];
            //机器人有体积 不能走最外围一圈
            if(yy+1>m||xx+1>n||xx-1<0||yy-1<0)continue;

            bool flag=false;
            //判断是否在前进的路上有没有石头
            for(int ii=t.x,jj=t.y;;)
            {

                if(a[ii][jj]==1||a[ii][jj+1]==1||a[ii+1][jj]==1||a[ii+1][jj+1]==1)
                {
                    flag=true;
                    break;
                }
                if(t.fang==1)
                {
                    jj++;
                    if(jj>yy)break;
                }
                else if(t.fang==2)
                {
                    jj--;
                    if(jj<yy)break;
                }
                else if(t.fang==3)
                {
                    ii--;
                    if(ii<xx)break;
                }
                else
                {
                    ii++;
                    if(ii>xx)break;
                }
            }
            if(flag)continue;
            if(!vis[xx][yy][t.fang])
            {

                vis[xx][yy][t.fang]=true;
                q.push(Node{xx,yy,t.fang,t.time+1});
            }
        }
        int f1,f2;
        //左右转向
        if(t.fang==1||t.fang==2)f1=3,f2=4;
        else f1=1,f2=2;
        if(!vis[t.x][t.y][f1])
        {
            vis[t.x][t.y][f1]=true;
            q.push(Node{t.x,t.y,f1,t.time+1});
        }
        if(!vis[t.x][t.y][f2])
        {
            vis[t.x][t.y][f2]=true;
            q.push(Node{t.x,t.y,f2,t.time+1});
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
    }
    scanf("%d%d%d%d%*c%c",&x1,&y1,&x2,&y2,&fang);
    int flag=0;
    if(fang=='E')flag=1;
    else if(fang=='W')flag=2;
    else if(fang=='N')flag=3;
    else flag=4;
    //cout<<flag<<endl;
    //cout<<x1<<y1<<x2<<y2<<endl;
    Node p;
    p.x=x1;
    p.y=y1;
    p.fang=flag;
    p.time=0;

    int o=bfs(p);
    if(o==-1)puts("-1");
    else printf("%d\n",o);

    //cout<<t.s<<endl;

    return 0;
}