这道题目真是非常坎坷啊，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][][],n,m,go[][]={{-,},{,},{,},{,-}};///注意按照自己规定的方向处理数组，便于行走
priority_queue<Node> que;
bool ok(Node a){
if(a.x>=&&a.x<n && a.y>=&&a.y<m && state[a.x][a.y][a.col][a.dir]== && maps[a.x][a.y]!='#') return true;
return false;
}
void mark(Node a){
state[a.x][a.y][a.col][a.dir] = ;
}
int BFS(Node s){
while(!que.empty()) que.pop();
que.push(s);
state[s.x][s.y][s.col][s.dir] = ;
while(!que.empty()){
Node now = que.top();
que.pop();
if(maps[now.x][now.y]== 'T' && now.col==) return now.tim;
Node nxt = now;
nxt.tim++;///每一次操作，耗费1s
nxt.dir = (now.dir + )%;
if(ok(nxt)){que.push(nxt); mark(nxt);}
///第一种向右转，注意是转 nxt.dir = now.dir - ; if(nxt.dir<) nxt.dir=;
if(ok(nxt)){que.push(nxt); mark(nxt);}
///第二种向左转 nxt.dir = now.dir;
nxt.col=(now.col+)%;
nxt.x = go[now.dir][] + now.x;
nxt.y = go[now.dir][] + now.y;
///向所在方向行走，并且改变颜色
if(ok(nxt)) {que.push(nxt); mark(nxt);}
}
return -;
}
int main()
{
int ca = ;
while(EOF != scanf("%d%d",&n,&m)){
if(n==&& m==) break;
if(ca) printf("\n"); ///注意不要多输出空行
for(int i = ;i < n;i++)
scanf("%s",maps[i]);
Node start;
memset(state,,sizeof(state));
for(int i = ;i < n;i++){
for(int j = ;j < m;j++){
if(maps[i][j]=='S'){
start.x = i; start.y = j;
start.col=; start.dir=;
start.tim = ;
}
}
}
int ans = BFS(start);
printf("Case #%d\n",++ca);
if(ans == -) printf("destination not reachable\n");
else printf("minimum time = %d sec\n",ans);
}
return ;
}