這題出得不錯，在傳統(tǒng)的bfs上加了點改進，好題~
#include<iostream>
#include<cmath>
using namespace std;
int const maxn=110;
int mm[maxn][maxn];
int v[maxn][maxn][4];//0上，1右，2下，3左
struct node
{
int step;
int x,y;
int dir;
}q[10000000];
int n,m;
int t;
int sx,sy;
int tx,ty;
void input()
{
scanf("%d%d",&n,&m);
char s[200];
int i;
for(i=0;i<n;i++)
{
scanf("%s",s);
int len=strlen(s);
for(int j=0;j<len;j++)
{
if(s[j]=='#')mm[i][j]=-1;
else if(s[j]=='.')mm[i][j]=0;
else if(s[j]=='S'){sx=i;sy=j;mm[i][j]=0;}
else if(s[j]=='T'){tx=i;ty=j;mm[i][j]=0;}
}
}
}
bool god(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m&&mm[x][y]!=-1)
return true;
else
return false;
}
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int main()
{
int l,r;
int i,j;
scanf("%d",&t);
while(t--)
{
memset(v,0,sizeof(v));
input();
//
l=r=1;
q[l].step=0;
q[l].dir=0;
q[l].x=sx;
q[l].y=sy;
v[sx][sy][0]=1;
//初始化
while(l<=r)
{
if(q[l].x==tx&&q[l].y==ty)
break;
for(i=0;i<4;i++)
{
if(i==q[l].dir)
{
int nx=q[l].x+dir[i][0];
int ny=q[l].y+dir[i][1];
if(god(nx,ny)&&v[nx][ny][i]==0)
{
v[nx][ny][i]=1;
r++;
q[r].x=nx;
q[r].y=ny;
q[r].step=q[l].step+1;
q[r].dir=q[l].dir;
}
}
else
{
int nr=(q[l].dir+1)%4;
int nl=(((q[l].dir-1)%4+4)%4);
if(v[q[l].x][q[l].y][nr]==0)
{
v[q[l].x][q[l].y][nr]=1;
r++;
q[r].x=q[l].x;
q[r].y=q[l].y;
q[r].step=q[l].step+1;
q[r].dir=nr;
}
if(v[q[l].x][q[l].y][nl]==0)
{
v[q[l].x][q[l].y][nl]=1;
r++;
q[r].x=q[l].x;
q[r].y=q[l].y;
q[r].step=q[l].step+1;
q[r].dir=nl;
}
}
}
l++;
}
if(l<=r)
printf("%d\n",q[l].step);
else
printf("-1\n");
}
return 0;
}