题目描述 机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径$1.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自己开这个题是在4月18号，过去了一个多月，从10分到100都得过，今天终于明白并A了。 感觉这个题坑真的挺多的。
块和点的转换，这个还比较明显。边界不能走，一开始没有看出来…方向由字母ESWN转化为0123，这样在bfs搜的时候转换方向很方便。经学习别人代码，发现X数组和Y数组的数字设定实在是很巧妙，在搜索时根据0123直接可以把走的距离加上去。第六个数据点的WA，地图上的障碍和已经走过的位置不能用一种方法标记。用一种的时候看讨论说 在搜索的时候把向前走和换方向的位置换一下 结果的确AC了，不过很玄学，正确的应该是在向前走的时候的判定，向前走时，如果遇到障碍点，就得直接break，不能再继续往前走了，但如果遇到的是已经走过的点，则应该continue，可以继续往下走。 #include<iostream> #include<queue> #include<cstring> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=60; int n,m; int X[4]={0,1,0,-1}; int Y[4]={1,0,-1,0}; //感觉这两个数组的设定很巧妙 struct node{ int x,y; int dir; int step; }S,E,Node; int G[maxn][maxn]; bool inq[maxn][maxn][4]; bool d[maxn][maxn]; bool test(int x,int y,int z){ if(inq[x][y][z]&&x>0&&x<n&&y>0&&y<m&&d[x][y]) return true; return false; } int bfs(int x,int y){ queue<node> q; S.step=0; q.push(S); while(!q.empty()) { node top=q.front(); q.pop(); if(top.x==E.x&&top.y==E.y) return top.step; int newx=top.x; int newy=top.y; for(int i=0;i<3;i++) { newx+=X[top.dir]; newy+=Y[top.dir]; if(test(newx,newy,top.dir)) //如果该点既没有走过，也不是障碍点，也不是边界点的话 { Node.x=newx; Node.y=newy; Node.dir=top.dir; Node.step=top.step+1; inq[newx][newy][top.dir]=false; q.push(Node); } else if(d[newx][newy]==false) //如果该点不能走是因为是障碍点的话，那么就不能继续往前走 break; else if(inq[newx][newy][top.dir]==false) //如果该点不能走是因为已经走过的话，那么可以继续向前走。 continue; } Node.x=top.x; Node.y=top.y; int d=top.dir; d--; if(d<0) d=3; Node.dir=d; Node.step=top.step+1; if(test(Node.x,Node.y,Node.dir)) { inq[Node.x][Node.y][Node.dir]=false; q.push(Node); } d=top.dir; d++; if(d>3) d=0; Node.dir=d; Node.step=top.step+1; if(test(Node.x,Node.y,Node.dir)) { inq[Node.x][Node.y][Node.dir]=false; q.push(Node); } } return -1; } int main() { cin>>n>>m; mem(inq,true); mem(d,true); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>G[i][j]; if(G[i][j]==1) { for(int k=0;k<4;k++) { d[i][j]=false; d[i+1][j]=false; d[i][j+1]=false; d[i+1][j+1]=false; } } } } cin>>S.x>>S.y>>E.x>>E.y; char c; cin>>c; if(c=='E') S.dir=0; else if(c=='S') S.dir=1; else if(c=='W') S.dir=2; else if(c=='N') S.dir=3; int ans=bfs(S.x,S.y); cout<<ans<<endl; return 0; }