题目：
Description
机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：先前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
Input
输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
Output
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
思路：
- map：记录是否能走
- flag：记录当前状态是否出现
- dir：记录向四个方向走横纵坐标的变化
- a：当前坐标向左向右转分别代表的数字
- 0——N，1——W，2——S，3——E
现将格图转换为点图(自己画图模拟),输入的障碍坐标应为点图的左上角,此时要将余下3个点标为假,起点和终点的坐标都要+1
void change(int i,int j)
{
map[i][j]=false;
map[i+1][j]=map[i][j+1]=map[i+1][j+1]=false;
}
void init()
{
memset(map,1,sizeof(map));
scanf("%d%d",&n,&m);
int a;
char b;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
scanf("%d",&a);
if (a) change(i,j);
}
cin>>sx>>sy>>ex>>ey>>b;
sx++; sy++; ex++; ey++;
if (b=='N') f[1].d=0;
else if (b=='W') f[1].d=1;
else if (b=='S') f[1].d=2;
else f[1].d=3;//判断机器人起点时的面向方向
}
BFS中判断是否到达终点,到达立即输出。先改变机器人的面向方向,加入队列;再枚举走的步数。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=55;
struct ss
{
int x,y,d,ans;
}f[N*N*5];
bool map[N][N],flag[N][N][N];
int n,m,sx,sy,ex,ey;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int a[3][4]={{0,1,2,3},{1,2,3,0},{3,0,1,2}};
void change(int i,int j)
{
map[i][j]=false;
map[i+1][j]=map[i][j+1]=map[i+1][j+1]=false;
}
void init()
{
memset(map,1,sizeof(map));
scanf("%d%d",&n,&m);
int a;
char b;
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
scanf("%d",&a);
if (a) change(i,j);
}
cin>>sx>>sy>>ex>>ey>>b;
sx++; sy++; ex++; ey++;
if (b=='N') f[1].d=0;
else if (b=='W') f[1].d=1;
else if (b=='S') f[1].d=2;
else f[1].d=3;
}
bool pd(int i,int j)
{
if (i<=1||i>n||j<=1||j>m) return false;
return true;
}
void bfs()
{
int l=0,r=1;
f[1].x=sx; f[1].y=sy; f[1].ans=0;
while (l<r)
{
l++;
if (f[l].x==ex&&f[l].y==ey)
{
printf("%d\n",f[l].ans); return;
}
int xx,yy,di;
for (int i=1; i<=2; i++)
{
di=a[i][f[l].d];
if (!flag[f[l].x][f[l].y][di])
{
flag[f[l].x][f[l].y][di]=true;
r++;
f[r].x=f[l].x; f[r].y=f[l].y; f[r].ans=f[l].ans+1; f[r].d=di;
}
}
for (int i=1; i<=3; i++)
{
xx=f[l].x+i*dir[f[l].d][0];
yy=f[l].y+i*dir[f[l].d][1];
if (map[xx][yy]&&pd(xx,yy))
{
if (!flag[xx][yy][f[l].d])
{
flag[xx][yy][f[l].d]=true;
r++;
f[r].x=xx; f[r].y=yy; f[r].ans=f[l].ans+1; f[r].d=f[l].d;
}
}
else break;
}
}
printf("-1\n");
}
int main()
{
init();
bfs();
return 0;
}