P1126 机器人搬重物

admin

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

倚窗倾听风吹雨

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.     }
    
35. 
    
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. }
    

复制代码