题目描述

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

输入输出格式
输入格式：
第一行为两个正整数，下面NN行是储藏室的构造，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

思路：一道很练代码实现能力的暴搜题，重点是这道题有很多坑，比如，横纵坐标问题，转弯问题，边界与半径的关系问题，在搜索的过程中注意一下即可。实现思路是bfs。首先，对于半径来说，每一个障碍的左边一个格子，上面一个格子，和左上角的那个格子，都是不能放东西的，但是由于题目障碍是格子。因此其对称位置就可以放，比如右下，下面，和右边，都可以放，我们可以直接在输入的时候把不符合条件的格子去掉。然后从起点开始搜索，知道找到符合条件的就立即输出退出程序，方向翻转的话，就随便歪歪一下就可以了，用一个队列维护点的坐标和方向即可。

希望这篇题解对大家能有所帮助。

代码：

#include<bits/stdc++.h>
#define maxn 57
using namespace std;
int n,m,a[maxn][maxn],sx,sy,ex,ey,vis[maxn][maxn][5],dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
char s;
struct node {
  int x,y,step,fx;
};
inline int get(char s) {
  if(s=='N') return 1;
  else if(s=='S') return 2;
  else if(s=='W') return 3;
  else return 4;
}
inline void bfs() {
  queue<node>q;
  if(sx>=n||sx<1||sy>=m||sy<1||a[sx][sy]) {puts("-1");exit(0);}
  vis[sx][sy][get(s)]=1;
  q.push((node){sx,sy,0,get(s)});
  while(!q.empty()) {
    node u=q.front();
    q.pop();
    int nx=u.x,ny=u.y;
    if(nx==ex&&ny==ey) {printf("%d\n",u.step);exit(0);}
    for(int i=1;i<=3;++i) {
      nx+=dx[u.fx],ny+=dy[u.fx];
      if(nx>=n||nx<1||ny>=m||ny<1||a[nx][ny]) break;
      if(!vis[nx][ny][u.fx]) {
        vis[nx][ny][u.fx]=1;
        q.push((node){nx,ny,u.step+1,u.fx});
      }
    }
    nx=u.x,ny=u.y;
    if(u.fx==1||u.fx==2) {
      if(!vis[nx][ny][3]) vis[nx][ny][3]=1,q.push((node){nx,ny,u.step+1,3});
      if(!vis[nx][ny][4]) vis[nx][ny][4]=1,q.push((node){nx,ny,u.step+1,4});
    } else {
      if(!vis[nx][ny][1]) vis[nx][ny][1]=1,q.push((node){nx,ny,u.step+1,1});
      if(!vis[nx][ny][2]) vis[nx][ny][2]=1,q.push((node){nx,ny,u.step+1,2});
    }
  }
}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i) {
    for(int j=1;j<=m;++j) {
      scanf("%d",&a[i][j]);
      if(a[i][j]==1)
        a[i-1][j-1]=a[i-1][j]=a[i][j-1]=1;
    }
  }
  scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
  if(ex>=n||ex<1||ey>=m||ey<1||a[ex][ey]) return puts("-1"),0;
  cin>>s;
  bfs();
  puts("-1");
  return 0;
}