题目描述
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.61.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个 N \times MN×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动11步（Creep）；向前移动2步（Walk）；向前移动33 步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为11 秒。请你计算一下机器人完成任务所需的最少时间。
输入格式
第一行为两个正整数N,M(N,M \le 50)N,M(N,M≤50)，下面NN行是储藏室的构造，00表示无障碍，11表示有障碍，数字之间用一个空格隔开。接着一行有44个整数和11个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东EE，南SS，西WW，北NN），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-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
输出 #1复制
12
#include <stdio.h>
#include <string.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
/*总结 BFS
细节有很多
1.注意特判！！！！ 当原点和终点相同时 直接输出 0
2.注意机器人所占位置为4个格子 写一个check函数 判断机器人能否在当前的位置
其中细节就是 注意四个点位 都不能越界 其次就是 不能是障碍物
3.一定要注意啊！！！！ 转一个方向需要一秒！！！！ 没注意到这个 卡了三小时！！！！！！！
4.此时一定要注意 第一次搜到的目标点不一定是最优解
5.一定要等全部搜完之后，标记出的地图坐标才是最优解
*/const int inf = 0x3f3f3f3f;
struct node
{
int x;
int y;
int d;
int sum;
node(int tx, int ty, int td, int tsum)
{
x = tx;
y = ty;
d = td;
sum = tsum;
}
};
int n = 0;
int m = 0;
int maze[100][100];
int vis[100][100];
int sx = 0;
int sy = 0;
int ex = 0;
int ey = 0;
int nd = 0;
int dx[] = {0, 1, 0, -1};
int dy[] = { 1,0,-1,0 };
int tx1[] = { 0,0,1,1 };
int ty1[] = { 0,1,1,0 };
int check(int x, int y)//判断当前坐标是否能够到达
{
int i = 0;
for (i = 0; i < 4; i++)//机器人占领4个格子，四个格子都要满足条件
{
int tx = x + tx1[i];
int ty = y + ty1[i];
if (tx < 1 || tx > n || ty < 1 || ty > m || maze[tx][ty] == 1 )//不能越界，且不能为障碍物
{
return 0;
}
}
return 1;
}
void bfs()
{
for (int i = 0; i <= n+10; i++)//初始化标记数组
{
for (int j = 0; j <= m+10; j++)
{
vis[i][j] = inf;
}
}
queue<node> q;
q.push(node(sx, sy, nd, 0));
vis[sx][sy] = 0;
while (q.size())//此时bfs的任务是标记地图
{
int x = q.front().x;
int y = q.front().y;
int d = q.front().d;
int sum = q.front().sum;
q.pop();
int i = 0;
int j = 0;
for (i = 0; i < 4; i++)//四个方向
{
for (j = 1; j <= 3; j++)//三个步数
{
int tx = x + dx[i] * j;
int ty = y + dy[i] * j;
if (check(tx, ty) == 0)//大步数取决于小步数，第一步都踏不出去，更别说第二步，第三步了
{
break;
}
int tsum = sum + 1;//移动时间1秒
//一定要注意！！！一秒只能转一个方向
//所以转向时间取决于转向幅度
if (abs(i - d) == 1 || abs(i-d) == 3)
{
tsum += 1;
}
else if (abs(i - d) == 2)
{
tsum += 2;
}
if (tsum >= vis[tx][ty])//只需要标记最小值
{
continue;
}
vis[tx][ty] = tsum;//更新最小值
q.push(node(tx, ty, i, tsum));
}
}
}
if (vis[ex][ey] == inf)//输出答案
{
cout << -1;
}
else
{
cout << vis[ex][ey];
}
}
int main()
{
cin >> n >> m;
int i = 0;
int j = 0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
cin >> maze[i][j];//读入地图
}
}
char ch = 0;
cin >> sx >> sy >> ex >> ey >> ch;
if (check(sx, sy) == 0)//判断起始点是否存在
{
cout << -1;
return 0;
}
else if (sx == ex && sy == ey)//一定注意起点与终点重合的特判！
{
cout << 0;
return 0;
}
switch(ch)
{
case 'D': nd = 0; break;
case 'S':nd = 1; break;
case'W':nd = 2; break;
case'N':nd = 3; break;
}
bfs();//开始标记整张地图，标记后的地图 坐标表示到达该点的最短步数
}