机器人搬重物(洛谷-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。
输入输出样例
输入样例#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;
}