题目描述
机器人移动学会(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. 四格移动,所以这四个无障碍物体且机器人中心不能在边界。
2. 东南西北行动且一次只能向右向左转,这是这题难点,首先我们可以把东南西北走法放进我们平常的两个数组,我们一开始先按照上一个方向去走,然后,我们再翻转90和180 记录数据。
具体细节看代码。
代码实现:
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,fx,fy,i,j;
int dx[5]={0,0,1,0,-1}, //东南西北走法dy[5]={0,1,0,-1,0};
int a[55][55],v[55][55];
int qx[1000000],qy[1000000],f[1000000],ans[1000000]={0},fz[1000000];
//qx,qy记录坐标,f记录方向,ans记录时间,fz判断翻转是否重复
char ch;
int main()
{cin>>n>>m;for(i=1;i<=n;i++)for(j=1;j<=m;j++){cin>>a[i][j];v[i][j]=a[i][j];}cin>>sx>>sy>>fx>>fy;cin.get();cin>>ch;if(sx==fx&&sy==fy) //特殊情况{cout<<"0"<<endl;return 0;}if(v[fx][fy]==1) //特殊情况{cout<<"-1"<<endl;return 0;}//bfs开始int tail=1,head=0;qx[1]=sx;qy[1]=sy;v[sx][sy]=1;if(ch=='E') f[1]=1; //判断初始方向else if(ch=='S') f[1]=2;else if(ch=='w') f[1]=3;else if(ch=='N') f[1]=4;int x,y,x1,y1,x2,y2,x3,y3;do{head++;//原来方向
///for(i=1;i<=3;i++){x=qx[head]+dx[f[head]]*i;y=qy[head]+dy[f[head]]*i;x1=x+1;y1=y;//机器人占据四格x2=x;y2=y+1;x3=x+1;y3=y+1;if(x>=1&&x+1<=n&&y>=1&&y+1<=m&&a[x][y]==0&&a[x1][y1]==0&&a[x2][y2]==0&&a[x3][y3]==0)//注意边界条件{if(v[x][y]==0){tail++;qx[tail]=x;qy[tail]=y;f[tail]=f[head]; //方向不变ans[tail]=ans[head]+1;v[x][y]=1;if(x==fx&&y==fy) //找到答案{cout<<ans[tail]<<endl;return 0;}}}else break;//一格都前进不了,剩下就不可能了}//翻转90if(fz[head]==0)//代表该状态不是有旋转得到,避免重复旋转{for(j=1;j<=4;j++)if(j!=f[head]){if(j!=f[head]+2&&j!=f[head]-2){tail++;qx[tail]=qx[head];//坐标不变qy[tail]=qy[head];f[tail]=j; //方向变了ans[tail]=ans[head]+1;fz[tail]=1;}}//180
//for(j=1;j<=4;j++)if(j!=f[head]){if(j==f[head]+2||j==f[head]-2){tail++;qx[tail]=qx[head];qy[tail]=qy[head];f[tail]=j;ans[tail]=ans[head]+2;fz[tail]=1;}}}}while(head<tail);cout<<"-1"<<endl;return 0;
}