洛谷P1126 机器人搬重物

题目描述

机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径 $1.6 米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个 N×MN \times MN×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动 111 步（Creep）；向前移动2步（Walk）；向前移动 333 步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为 111 秒。请你计算一下机器人完成任务所需的最少时间。

输入格式：

第一行为两个正整数 N,M(N,M≤50)N,M(N,M \le 50)N,M(N,M≤50) ，下面 NNN 行是储藏室的构造， 000 表示无障碍， 111 表示有障碍，数字之间用一个空格隔开。接着一行有 444 个整数和 111 个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东 EEE ，南 SSS ，西 WWW ，北 NNN ），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式：

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出 −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

输出样例：

12

思路：

这道题坑真多QAQ 输入是格子图 要转化为点阵 另外机器人有直径 注意不能越界 障碍物周围的四个点全部不能走 代码比较长 还要处理转弯.......

#include<iostream>
#include<cstring>
using namespace std;
int n,m,x1,x2,y1,y2,vis[51][51],dirs,minn=0x7ffffff,ans[1001]={-1},tot;
char dir;
int f[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}}; 
bool a,map[55][55];
struct ljq {
	int x,
	    y,
	    dir,
	    step;
}q[5001];//定义结构体 x y 为当前坐标 dir为所对方向 step为步数
int h=1,t;//队头队尾
int main()
{
    cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=m; j++)
		{
			cin>>a;..输入
			if(a==1)
			{
				map[i-1][j-1]=1;
				map[i-1][j]=1;
				map[i][j-1]=1;
				map[i][j]=1;//把格子图转化为点阵 障碍物周围的点标记为1
			}
		}
	}
	for(int i=1; i<=n; i++)
	{
		map[n][i]=1;
		map[i][m]=1;//将边界标记成1
	}
	cin>>x1>>y1;
	cin>>x2>>y2;
	cin>>dir;//输入
	q[++t].x=x1;
	q[t].y=y1;
	q[t].step=0;//初始化搜索
	if(dir=='E')
	{
		q[t].dir=1;
	}
	else if(dir=='W')
	{
		q[t].dir=2;
	}
	else if(dir=='S')
	{
		q[t].dir=3;
	}
	else if(dir=='N')
	{
		q[t].dir=4;//方向变成数字
	}
	memset(vis,999999,sizeof(vis));把最优解数组置为较大的数
	while(h<=t)//广搜开始
	{
		if(q[h].x==x2&&q[h].y==y2)
		{
			ans[++tot]=q[h].step;//如果满足条件 
		}
		for(int i=1;i<=4;i++)//四个方向
		{
			int dirs=q[h].step;
			if(i!=q[h].dir) //如果方向不同 步数+1；
			{
				dirs=q[h].step+1;
				if(i==1&&q[h].dir==2||i==2&&q[h].dir==1||i==3&&q[h].dir==4||i==4&&q[h].dir==3)//如果需要向后转 步数+2
				{
					dirs=q[h].step+2;
				}
			}
			for(int j=1;j<=3;j++)//前进1或2或3格
		    {
			    int lx=q[h].x+j*f[i][0];//目标点坐标
				int ly=q[h].y+j*f[i][1];
			    if(lx>n||lx<1||ly>m||ly<=0||map[lx][ly])//如果进入边界或碰到障碍物 循环停止
			    {
			    	break;
				}
				if(dirs<vis[lx][ly])//最优解
				{
					q[++t].x=lx;q[t].y=ly;//下一个点的坐标
					q[t].step=dirs+1; q[t].dir=i;
					vis[lx][ly]=dirs;
				}
		    }
		}
		h++;
	}
	for(int i=1;i<=tot;i++)
	{
		if(ans[i]<minn)
		{
			minn=ans[i];//答案
		}
	}
	if(minn<0x7ffffff) cout<<minn;//如果minn发生改变 有答案 输出minn
	else cout<<-1;//无答案输出-1
	return 0;
}

蒟蒻一只......题解写的不太好......