做题感悟：这道题属于一般的搜索题，要注意一些细节，输出的时候检查是否与样例一样。
解题思路：这题终点在标记上面，因为题目中有方向和颜色限制，so~> 需要一个四维数组来标记，如果做过POJ上的左手定则这题应该很容易做。
代码：
#include<stdio.h>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std ;
const int MX = 30 + 10 ;
int n,m ;
char s[MX][MX] ;
bool vis[MX][MX][MX][MX] ;
int dx[5]={1,-1,0,0,0},dy[5]={0,0,1,-1,0} ;
int dt[4][4]={{2,4,4},{3,4,4},{0,4,4},{1,4,4}} ;
int dw[4][4]={{0,2,3},{1,2,3},{2,0,1},{3,0,1}} ;
struct node
{
int x,y,step,drt,clr ;
} ;
bool judge(int x,int y)
{
if(x<0||y<0||x>=n||y>=m||s[x][y]=='#')
return false ;
return true ;
}
int bfs(int x,int y) // 东西南北 0 1 2 3
{
queue<node>q ;
node curt,next ;
memset(vis,false,sizeof(vis)) ;
curt.x=x ;
curt.y=y ;
curt.step=0 ; // 时间
curt.clr=0 ; // 颜色
curt.drt=3 ; // 方向
q.push(curt) ;
vis[x][y][0][3]=true ; // 颜色+方向
while(!q.empty())
{
curt=q.front() ;
if(s[curt.x][curt.y]=='T'&&curt.clr==0)
return curt.step ;
q.pop() ;
int cnt=curt.drt ;// 主方向
for(int i=0 ;i<3 ;i++)
{
int tx=dt[cnt][i] ;
next.x=curt.x+dx[tx] ;
next.y=curt.y+dy[tx] ;
if(i)
next.clr=curt.clr ;
else next.clr=(curt.clr+1)%5 ;
next.step=curt.step+1 ;
next.drt=dw[cnt][i] ;
if(judge(next.x,next.y)) // 判断出界
{
if(vis[next.x][next.y][next.clr][next.drt]) continue ;
vis[next.x][next.y][next.clr][next.drt]=true ;
q.push(next) ;
}
}
}
return -1 ;
}
int main()
{
int sx,sy,cse=1 ;
while(~scanf("%d%d",&n,&m)&&(n+m))
{
for(int i=0 ;i<n ;i++)
{
scanf("%s",s[i]) ;
for(int j=0 ;j<m ;j++)
if(s[i][j]=='S')
{
sx=i ;
sy=j ;
}
}
int mx=bfs(sx,sy) ;
if(cse!=1) cout<<endl ;
cout<<"Case #"<<cse++<<endl ;
if(mx==-1)
cout<<"destination not reachable"<<endl ;
else cout<<"minimum time = "<<mx<<" sec"<<endl ;
}
return 0 ;
}