欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[洛谷]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。

[洛谷]P1126 机器人搬重物 (#搜索)

 

输入输出样例

输入样例#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;
}