[洛谷]P1126 机器人搬重物 (#搜索)
程序员文章站
2022-06-12 09:46:37
...
题目描述
机器人移动学会(RMI
)现在正尝试用机器人搬运物品。机器人的形状是一个直径$1.6米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个N \times MN×M的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动11步(Creep
);向前移动2步(Walk
);向前移动33步(Run
);向左转(Left
);向右转(Right
)。每个指令所需要的时间为11秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式:
第一行为两个正整数N,M(N,M≤50),下面NN行是储藏室的构造,00表示无障碍,11表示有障碍,数字之间用一个空格隔开。接着一行有44个整数和11个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东EE,南SS,西WW,北NN),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式:
一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出-1−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
思路
这题很阴......我拿小号提交了快20次......一直30、50、60、70、90分,就是A不了!
首先要转成点图,因为障碍物是在格子上的,而机器人在点上。注意边界不可以走,因为机器人本身是有半径的。
还有一点就是方向和下一步要走的似乎要对应,不然60分。
另外机器人本身是否在终点还有特判一次......
其实本题很考验码力,细节处理的也有很多。(我写了122行)
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
typedef struct
{
int x,y;//每个点的坐标
int len;//当前点的步长
int d;//方向
}lxydl;
int a[56][56],squ[56][56],n,m,s,inx,iny,outx,outy;
queue<lxydl> que;
int tox[4]={0,1,0,-1},toy[4]={1,0,-1,0};//下一个点一定要和td方向数组对应!!我之前一直30、50、60分
int td[4]={1,2,3,4};
char direc;
inline bool check(int x,int y)
{
if(x>=2 && x<=n && y>=2 && y<=m)
{
return 1;
}
return 0;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
register int i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];//输入格点图
if(a[i][j]==1)//转化成点图
{
squ[i+1][j+1]=-1;
squ[i+1][j]=-1;
squ[i][j+1]=-1;
squ[i][j]=-1;
}
}
}
cin>>inx>>iny>>outx>>outy>>direc;
lxydl position;
if(inx==outx && iny==outy)//特判一下,节省时间
{
cout<<0<<endl;
return 0;
}
position.x=inx+1;//当格点图转点图时,所有坐标要+1
position.y=iny+1;
position.len=0;
if(direc=='E') position.d=1;//处理初始方向
else if(direc=='S') position.d=2;
else if(direc=='W') position.d=3;
else position.d=4;
que.push(position);//初始点入队
squ[position.x][position.y]=1;//标记走过了,而且标记的是当前步长
while(!que.empty())
{
int x1,y1,to,l;
for(i=0;i<=3;i++)//枚举方向
{
to=td[i];
if(que.front().d!=to)//如果当前方向和枚举方向不一样
{
if(to+que.front().d==4 || que.front().d+to==6)//如果是南北走向或者东西走向,要转2下,而加起来正好是6或4
{
l=que.front().len+2;
}
else//那么就是相邻的
{
l=que.front().len+1;//+1即可
}
}
else//如果是一样的
{
l=que.front().len;//不需要转弯
}
l++;
for(j=1;j<=3;j++)//走几步
{
x1=que.front().x+tox[i]*j;
y1=que.front().y+toy[i]*j;
if(x1==inx+1 && y1==iny+1 || squ[x1][y1]==-1)
{
break;
}
if(check(x1,y1))
{
if(squ[x1][y1]==0 || squ[x1][y1]>l)//如果不是障碍物,或发现了一条更短的路径
{
position.x=x1;
position.y=y1;
position.len=l;
position.d=to;
squ[x1][y1]=l;
/*if(x1==outx+1 && y1==outy+1)
{
cout<<l<<endl;
return 0;
}*/
que.push(position);
}
}
}
}
que.pop();
}
if(squ[outx+1][outy+1]==0)//注意要+1
{
cout<<-1<<endl;
}
else
{
cout<<squ[outx+1][outy+1]<<endl;
}
return 0;
}