题解 P1126 【机器人搬重物】

fengzi8615 · 2018-09-07 18:04:56 · 个人记录

BFS水题

主要难点在于初始化

我们要初始化哪些地方不能走,还要初始化一开始的时候要怎么转弯

接着我们要考虑BFS遍历的时候,要怎么更新当前点方向

这些能弄懂,那代码一下子就写出来了

Code：

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

using namespace std;

int n,m,map[51][51];
int num;
int vis[51][51];
//vis储存访问过的取到的最小值 
int head=1,tail=0;
int ans[5001]={0},tot,mina=0x7ffffff;
//minad储存最小值 

//用于BFS的数组,前后左右移动 
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};

struct fengzi
{
    int x,y,direct,step;
}q[5001];
//direct储存这个点的方向
//step储存从起点出发到这个点的步数 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int no;
            scanf("%d",&no);
            if(no)
            {
                map[i][j]=1;
                map[i-1][j-1]=1;
                map[i-1][j]=1;
                map[i][j-1]=1;
                //预处理不能走的地方 
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        map[n][i]=1;
        map[i][m]=1;
        //预处理四周 
    }

    int x0,y0,xt,yt;
    char BFS_wan_sui;
    scanf("%d %d %d %d %c",&x0,&y0,&xt,&yt,&BFS_wan_sui);

    tail++;
    q[tail].x=x0;
    q[tail].y=y0;
    q[tail].step=0;
    //初始化BFS 

    if(BFS_wan_sui=='E') q[tail].direct=1;
    else if(BFS_wan_sui=='W') q[tail].direct=2;
    else if(BFS_wan_sui=='S') q[tail].direct=3;
    else if(BFS_wan_sui=='N') q[tail].direct=4;
    //初始化起点的方向 
    memset(vis,0x7f,sizeof(vis));

    //BFS万岁 
    while(head<=tail)
    {
        if(q[head].x==xt&&q[head].y==yt)
        //记录答案 
        {
            ans[++tot]=q[head].step;
        }

        for(int i=1;i<=4;i++) 
        //4个方向走 
        {
            int step=q[head].step;
            if(i!=q[head].direct) 
            //如果这个点需要转一次弯 
            {
                step=q[head].step+1;
                if((i==1&&q[head].direct==2)||(i==2&&q[head].direct==1)||(i==3&&q[head].direct==4)||(i==4&&q[head].direct==3)) 
                //如果要向后转 
                  step=q[head].step+2;
            }
            for(int j=1;j<=3;j++) 
            //走一步,两步,或者三步 
            {
                int xx,yy;
                xx=q[head].x+j*dx[i];
                yy=q[head].y+j*dy[i]; 
                //开始移动 

                if(xx>n||xx<1||yy>m||yy<=0||map[xx][yy])  break;
                //如果走出了范围,直接退出循环 
                if(vis[xx][yy]>step) 
                //更新答案
                {
                    tail++;
                    q[tail].x=xx;
                    q[tail].y=yy;
                    q[tail].step=step+1; 
                    q[tail].direct=i;
                    //走这一步,更新方向,起点(x，y),以及步数 
                    vis[xx][yy]=step;
                }
            }
        }
        head++;
    }
    for(int i=1;i<=tot;i++) 
    {
        mina=min(mina,ans[i]);
        //找到最小答案 
    }

    if(mina<0x7fffff) cout<<mina;
    else cout<<-1;
    //元气满满的输出 

    return 0;
}