这道题目真是非常坎坷啊，WA了很多次，但所有的思路都是奔着广搜去想的，一开始出现了比答案大的数据，才想到了应该是优先队列，再说加上也肯定不会错。一开始我读错了题意，以为旋转并且前行需要的时间跟其他一样，但是旋转的动作是需要额外计时的。我的第一种方法错误原因还没有找到，我在旋转以后就直接改动了位置，感觉没有什么本质区别，旋转了以后，肯定要走啊，我直接加上时间也没什么问题，我也把所能想到的测试用例都试过了，与AC代码完全一致，真是搞不懂，这要是CF就好了。于是，学习了别人的代码，改了改我原先的地方，发现还真是那里错了。。又经过了一番钻研，才算优雅的AC了题目。
吐槽就到这里了，我来说一下代码吧。
状态使用四维数组保存，位置占两维，方向和颜色各占一维，颜色就是题目中给的5种颜色，方向最好给定一个标号，便于以后的行走。（0N ，1E, 2S，3W） ，在搜索过程中，每一次操作都将会耗费1秒种，操作分为向左右旋转，即改变dir，向目前的方向移动，改变x和y。 每次都让这3中新的状态进入优先队列，选择耗费时间小的作为队头，这样当搜索到的时候，便是耗费最小的步数。
#include<iostream> #include<cstdio> #include<map> #include<queue> #include<cstring> using namespace std; #define maxn 30 struct Node{ int x,y,col,dir,tim; bool operator < (Node a)const{ return a.tim < tim; } }; char maps[maxn][maxn]; int state[maxn][maxn][10][10],n,m,go[4][2]={{-1,0},{0,1},{1,0},{0,-1}};///注意按照自己规定的方向处理数组，便于行走 priority_queue<Node> que; bool ok(Node a){ if(a.x>=0&&a.x<n && a.y>=0&&a.y<m && state[a.x][a.y][a.col][a.dir]==0 && maps[a.x][a.y]!='#') return true; return false; } void mark(Node a){ state[a.x][a.y][a.col][a.dir] = 1; } int BFS(Node s){ while(!que.empty()) que.pop(); que.push(s); state[s.x][s.y][s.col][s.dir] = 1; while(!que.empty()){ Node now = que.top(); que.pop(); if(maps[now.x][now.y]== 'T' && now.col==0) return now.tim; Node nxt = now; nxt.tim++;///每一次操作，耗费1s nxt.dir = (now.dir + 1)%4; if(ok(nxt)){que.push(nxt); mark(nxt);} ///第一种向右转，注意是转 nxt.dir = now.dir - 1; if(nxt.dir<0) nxt.dir=3; if(ok(nxt)){que.push(nxt); mark(nxt);} ///第二种向左转 nxt.dir = now.dir; nxt.col=(now.col+1)%5; nxt.x = go[now.dir][0] + now.x; nxt.y = go[now.dir][1] + now.y; ///向所在方向行走，并且改变颜色 if(ok(nxt)) {que.push(nxt); mark(nxt);} } return -1; } int main() { int ca = 0; while(EOF != scanf("%d%d",&n,&m)){ if(n==0&& m==0) break; if(ca) printf(" "); ///注意不要多输出空行 for(int i = 0;i < n;i++) scanf("%s",maps[i]); Node start; memset(state,0,sizeof(state)); for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ if(maps[i][j]=='S'){ start.x = i; start.y = j; start.col=0; start.dir=0; start.tim = 0; } } } int ans = BFS(start); printf("Case #%d ",++ca); if(ans == -1) printf("destination not reachable "); else printf("minimum time = %d sec ",ans); } return 0; }