P1126 机器人搬重物

· · 题解

题目大意

机器人是一个直径1.6米的球。在N \times M 的网格中，有些格子不可移动,机器人可以向前移动1,2,3步；向左转，向右转。每个指令所需要的时间为1秒。请你计算最短到达指定位置的时间。

题目分析

这题用BFS来做

题目告诉我们机器人有体积，且只能行走在格点上，但障碍物是在格子中，所以最外围的一圈和方格的四周都是不能走的。

根据这一点我们可以在输入时对网格做处理，将机器人不能走的格点标记起来

我的方法跟别的都不太一样，是在判断下一步可以走哪个地方的时候用两个循环，第一个循环枚举方向，第二个循环枚举距离，就可以推出从当前格子走到目标格子需要的转向的时间和移动的时间。

但这种方法需要注意，最先到达一个格子的时间也不一定是当前格子的最优解，所以使用标记数组将当前最优时间记录下来，如果之后走到该格子的时间小于目前的最优解，就替换并继续搜索。

Code

#include <bits/stdc++.h>
using namespace std;
int ans=1e9,c,n,m,sx,sy,ex,ey,h,a[100][100],f[100][100];
int fx[5]={0,-1,0,1,0},fy[5]={0,0,1,0,-1}; 
char r;
struct node
{
    int x,y,time,head;  //坐标，时间，头朝向
};
queue<node>q;
void bfs()
{
    q.push((node){sx,sy,0,h});
    f[sx][sy]=1;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.x==ex&&now.y==ey)
            ans=min(ans,now.time);  //因为最先到达并不一定是最优解，所以要继续搜索
        for(int i=1;i<=4;i++)   //行走的方向
        {
            for(int j=1;j<=3;j++)   //距离
            {
                int s=abs(now.head-i);  // 转向所需的时间
                if(s>2)
                    s-=2;
                node next={now.x+fx[i]*j,now.y+fy[i]*j,now.time+s+1,i};
                //如果目标格子未走过或之前的最优解比现在需要的时间多，就入队
                if((f[next.x][next.y]==0||f[next.x][next.y]>next.time)&&a[next.x][next.y]==0&&next.x>=1&&next.x<n&&next.y>=1&&next.y<m) 
                    q.push(next),
                    f[next.x][next.y]=next.time;
                else
                    break;  //否则不能继续前进
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&c);
            if(c)       //如果当前格子为障碍物
                a[i-1][j-1]=a[i-1][j]=a[i][j-1]=a[i][j]=1;  //标记四个顶点
        }
    scanf("%d%d%d%d%s",&sx,&sy,&ex,&ey,&r);
    if(r=='N')  h=1;
    if(r=='E')  h=2;
    if(r=='S')  h=3;
    if(r=='W')  h=4;
    bfs();
    if(ans==1e9)    //没有改变则输出无法到达
        cout<<"-1";
    else
        cout<<ans;  
    return 0;
}