洛谷P1126 机器人搬重物

题目描述

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

输入输出格式

输入格式：

 

第一行为两个正整数 N,M(N,M≤50)，下面 N 行是储藏室的构造， 0 表示无障碍， 1 表示有障碍，数字之间用一个空格隔开。接着一行有 4个整数和 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

思路

这道题可以说是非常阴险了，本来只是一道很简单的广搜，结果被阴险的出题人硬生生地挖了好多坑，难度直接升到提高QAQ。

第一个坑：要将格子图转换为点图。

第二个坑：机器人是有半径的，所以要处理边界，而且障碍物周围的四个点都不能走。

第三个坑：方向非常麻烦，必须处理好。

只要解决了这几个坑 ，剩下的广搜就非常简单了，在这里不解释。

广搜模板：https://blog.csdn.net/zhuyifan_jizhi/article/details/81112014

代码

// 先看主函数是一种好习惯
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
bool map[51][51];
int vis[51][51][5];//行、列、方向 
int dx[4]= {0,1,0,-1},dy[4]= {1,0,-1,0};
struct node {
	int x,y,dir,step;//分别为行，列，方向，步数
};
queue<node> q;
node aaa;
int tx,ty,f,st,x1,x2,y1,y2,n,m;
int ans[5001]= {-1},tot,minl=0x7fffff;
int fx[5]= {0,1,0,-1},
           fy[5]= {1,0,-1,0};
void bfs() {
	while(!q.empty()) {
		aaa=q.front();
		q.pop();
		tx=aaa.x;
		ty=aaa.y;
		if(tx==x2 && ty==y2) {//满足条件，直接输出 
			printf("%d",aaa.step) ;
			return;
		}
		for(int j=1; j<=3; j++) {//1~3步 
			tx+=fx[aaa.dir];
			ty+=fy[aaa.dir] ;
			if( tx <= 0 || ty <= 0 || tx >= n || ty >= m || map[tx][ty]==1 )//如果到边界或遇到障碍，结束循环 
				break ;
			else if(!vis[tx][ty][aaa.dir]) {
				vis[tx][ty][aaa.dir]=true;
				node cnew;
				cnew.x=tx;
				cnew.y=ty;
				cnew.dir=aaa.dir;
				cnew.step=aaa.step+1;
				q.push(cnew);
			}
		}
		//还是处理方向(这里有些难理解) 
		//当碰到障碍，就会break到这里转向 
		node cnew;
		cnew.x=aaa.x;
		cnew.y=aaa.y;
		cnew.step=aaa.step+1;
		cnew.dir=aaa.dir-1;
		if(cnew.dir==-1)cnew.dir=3;//从东向西转，转到北 
		if(!vis[cnew.x][cnew.y][cnew.dir]) {
			vis[cnew.x][cnew.y][cnew.dir]=true;
			q.push(cnew);
		}
		cnew.dir=aaa.dir+1;
		if(cnew.dir==4)cnew.dir=0;//从北向东转，转到东 
		if(!vis[cnew.x][cnew.y][cnew.dir]) {
			vis[cnew.x][cnew.y][cnew.dir]=true;
			q.push(cnew);
		}
	}
	cout<<-1;
}
int main() {
	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;
	}
	char fang;
	cin>>x1>>y1>>x2>>y2>>fang;
	//处理方向 
	if(fang=='E') aaa.dir=0;
	else if(fang=='S') aaa.dir=1;
	else if(fang=='W') aaa.dir=2;
	else aaa.dir=3;
	aaa.x=x1;
	aaa.y=y1;
	aaa.step=0;
	q.push(aaa);
	bfs();
	return 0;
}