华师一附中OI组

标题: P1126 机器人搬重物 [打印本页]
作者: admin    时间: 2018-5-13 20:00
标题: P1126 机器人搬重物
https://www.luogu.org/problemnew/show/P1126


题目描述
机器人移动学会（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。



输入输出样例
输入样例#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
作者: 倚窗倾听风吹雨    时间: 2018-9-12 20:42
  1. #include<iostream>
  2. #include<queue>
  3. #include<cmath>
  4. using namespace std;
  5. const int M=55;
  6. struct node
  7. {
  8.     int t,r,c,time;
  9. }p;
  10. char ch;
  11. bool o[M][M],flag;
  12. queue<node>q;
  13. int n,m,gr,gc,vis[M][M],ans[5001],tot;
  14. int main()
  15. {
  16.     cin>>n>>m;
  17.     for(int i=1; i<=n; i++)
  18.         for(int j=1; j<=m; j++)
  19.         {
  20.             cin>>flag;
  21.             if(flag)
  22.             {
  23.                 o[i][j]=1;
  24.                 o[i-1][j-1]=1;
  25.                 o[i-1][j]=1;
  26.                 o[i][j-1]=1;
  27.             }
  28.             vis[i][j]=99999;
  29.         }
  30.         for(int i=1;i<=n;i++)
  31.     {
  32.         o[n][i]=1;
  33.         o[i][m]=1;
  34.     }

  36.     flag=0;
  37.     cin>>p.r>>p.c;
  38.     p.time=0;
  39.     cin>>gr>>gc;
  40.     cin>>ch;
  41.     if(ch=='N')
  42.         p.t=1;
  43.     if(ch=='E')
  44.         p.t=2;
  45.     if(ch=='S')
  46.         p.t=3;
  47.     if(ch=='W')
  48.         p.t=4;
  49.     q.push(p);
  50.     while(!q.empty())
  51.     {
  52.         if(q.front().r==gr && q.front().c==gc)
  53.             ans[++tot]=q.front().time;
  54.         for(int i=1; i<=4; i++)
  55.         {
  56.             p.t=q.front().t;
  57.             p.c=q.front().c;
  58.             p.r=q.front().r;
  59.             p.time=q.front().time+1;
  60.             if(i!=p.t)
  61.             {
  62.                 p.time++;
  63.                 if(abs(p.t-i)==2)p.time++;
  64.             }
  65.             p.t=i;
  66.             for(int j=1;j<=3;j++)
  67.             {
  68.                 if(i==1)p.r--;
  69.                 if(i==2)p.c++;
  70.                 if(i==3)p.r++;
  71.                 if(i==4)p.c--;
  72.                 if(o[p.r][p.c] || p.r<=0 || p.c<=0 || p.r>n || p.c>m)break;
  73.                 if(vis[p.r][p.c]>p.time)
  74.                 {
  75.                     q.push(p);
  76.                     vis[p.r][p.c]=p.time;
  77.                 }
  78.             }
  79.         }
  80.         q.pop();
  81.     }
  82.     if(tot==0)cout<<"-1"<<endl;
  83.     else
  84.     {
  85.         for(int i=1;i<=tot;i++)ans[1]=min(ans[1],ans[i]);
  86.         cout<<ans[1]<<endl;
  87.     }
  88.     return 0;
  89. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2