【广度搜索】 机器人搬重物

题目

题目描述

机器人移动学会（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

解法

我们假设从地图（1，1）开始输入地图各个坐标， ----注意，不能走到n 或 m 会出边界；
输入点为1时，就把这个点的上下左右都标记为1，表示一个黑格
当机器人红心点 为1时，表示不能走，撞墙了。

其他在代码里标注了。

代码

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

const int MAX_N = 55;
int n,m;

bool mp[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N][4];
int xx[]={-1,0,1,0};
int yy[]={0,1,0,-1};
int sx,sy,tx,ty;
struct data{
	int x,y,s,d;			//sx sy s步数 d方向 
};

bool in(int x,int y){
	return 1<=x &&x<n && 1<=y && y<m;											//注意，不能走到n 或 m 会出边界；
}																											
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int t;
			scanf("%d",&t);
			if(t){
				mp[i][j] = mp[i-1][j] = mp[i][j-1] = mp[i-1][j-1] = 1;					//把这个点的上下左右都标记为1，表示一个黑格 
			}
		}
	}
	queue<data> q;
	char tt;
	scanf("%d %d %d %d %c",&sx,&sy,&tx,&ty,&tt);			//输入
	data t1;
	t1.x=sx; t1.y=sy; t1.s=0 ;									
	if(tt =='N') t1.d = 0;																	//把方向转成数字
	if(tt =='E') t1.d = 1;																		
	if(tt =='S') t1.d = 2;
	if(tt =='W') t1.d = 3;
	q.push(t1);
	while(!q.empty()){
		data m = q.front();
		vis[m.x][m.y][m.d] = 1;								//当前位置 步数
		
		if(m.x == tx && m.y==ty){
			cout<<m.s;
			return 0;
		}
		data m1 = m;
		m1.s ++;
		m1.d = (m1.d+1)%4;   //E 左 									//每次 转向 就是 +几 mod 4 
		if(!vis[m1.x][m1.y][m1.d]) q.push(m1);
		
		m1.d = (m1.d+2)%4;		//W  右 					//左加 2 相当于转180  就是右
		if(!vis[m1.x][m1.y][m1.d]) q.push(m1);				//只有左右，没有后，后就得走两次左或右了
		
		//走一步 
		m1.d = m.d;
		m1.x = m1.x + xx[m1.d];
		m1.y = m1.y + yy[m1.d];
		if(in(m1.x,m1.y) && !vis[m1.x][m1.y][m1.d] && !mp[m1.x][m1.y]){
			q.push(m1);
			//再走一步 
			m1.x = m1.x + xx[m1.d];
			m1.y = m1.y + yy[m1.d];
			if(in(m1.x,m1.y) && !vis[m1.x][m1.y][m1.d] && !mp[m1.x][m1.y]){
				q.push(m1);
				//再走一步 
				m1.x = m1.x + xx[m1.d];
				m1.y = m1.y + yy[m1.d];
				if(in(m1.x,m1.y) && !vis[m1.x][m1.y][m1.d] && !mp[m1.x][m1.y]){
					q.push(m1);
				}
			}
		}
		q.pop();
	}
	cout<<-1;
	return 0;
}