欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

机器人搬重物(洛谷-P1126)

程序员文章站 2022-06-12 09:37:13
...

题目描述

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

输入输出格式

输入格式:

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

输出格式:

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

机器人搬重物(洛谷-P1126)

 

输入输出样例

输入样例#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

源代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 10001
using namespace std;
int dir[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}};
bool map[51][51];
int vis[51][51];
int head=1,tail;
struct node{
    int x;
    int y;
    int dir;
    int step;
}a[N];
int ans[5001]={-1};
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
          bool a;
          cin>>a;
          if(a)
          {
              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 sx,sy,ex,ey;
    char sdir;
    cin>>sx>>sy>>ex>>ey>>sdir;

    /*预处理*/
    a[++tail].x=sx;
    a[tail].y=sy;
    a[tail].step=0;
    if(sdir=='E')
      a[tail].dir=1;
    if(sdir=='W')
      a[tail].dir=2;
    if(sdir=='S')
      a[tail].dir=3;
    if(sdir=='N')
      a[tail].dir=4;

    memset(vis,1,sizeof(vis));

    int tot=0;
    int minl=INF;
    while(head<=tail)//搜索
    {
        if(a[head].x==ex&&a[head].y==ey)
            ans[++tot]=a[head].step;

        for(int i=1;i<=4;i++)
        {
            int step=a[head].step;
            if(i!=a[head].dir)//如果方向不一样,则需转弯,步数加一
            {
                step=a[head].step+1;
                if((i==1&&a[head].dir==2)||(i==2&&a[head].dir==1)||(i==3&&a[head].dir==4)||(i==4&&a[head].dir==3)) //如果向后转,需要转两次弯
                  step=a[head].step+2;
            }
            for(int j=1;j<=3;j++)//枚举步数
            {
                int xx=a[head].x+j*dir[i][0];
                int yy=a[head].y+j*dir[i][1];

                if(xx>n||xx<1||yy>m||yy<=0||map[xx][yy])
                    break;
                if(vis[xx][yy]>step)//保存最优解
                {
                    a[++tail].x=xx;
                    a[tail].y=yy;
                    a[tail].step=step+1;
                    a[tail].dir=i;
                    vis[xx][yy]=step;
                }
            }
        }
        head++;
    }
    for(int i=1;i<=tot;i++) //寻找最优解
    {
        if(ans[i]<minl)
          minl=ans[i];
    }

    if(minl<INF)
      cout<<minl;
    else
      cout<<-1;

    return 0;
}