2470. Robot in Maze ，一道宽度搜索的经典题目，但是我的一直是WA，请大家帮忙看看
原题网址：http://acm.tju.edu.cn/toj/showp2470.html
题意：S到T的最短路径，但是行走过程中改变方向的话步数要加1，输出最小步数，不能到达输出-1；

测试数据：
Sample Input
2
5 5
#####
#...#
#.#.#
#S#T#
#####
4 5
#.#.#
#.#.#
#S#T#
#####

Sample Output
8
-1


以下是我的代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

struct node{
int x,y;
int step;
char fx;
};
char map[110][110];
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int num[120];

int n,m;
int sx,sy,dx,dy;
bool flag;
node f;
int k1;
int bfs()
{
int i,j,k;
int tx,ty;
char temp;
int sstep;
queue<node>q;
node front,rear;
while(!q.empty())q.pop();
q.push(f);
while(!q.empty())
{
front=q.front();
q.pop();
if(front.x==dx&&front.y==dy){
num[k1++]=front.step;
flag=1;
}
map[front.x][front.y]='#';
for(i=0;i<4;i++)
{
tx=front.x+dir[i][0];
ty=front.y+dir[i][1];
if(dir[i][0]==-1&&dir[i][1]==0)temp='n';
if(dir[i][0]==1&&dir[i][1]==0)temp='s';
if(dir[i][0]==0&&dir[i][1]==1)temp='e';
if(dir[i][0]==0&&dir[i][1]==-1)temp='w';
if(front.fx!=temp)sstep=front.step+2;
else sstep=front.step+1;
if(tx<0||tx>=m||ty<0||ty>=n||map[tx][ty]=='#')continue;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=temp;
map[tx][ty]='#';
q.push(rear);
}
}
return 0;
}


int main()
{
int t,i,j,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
sx=i;
sy=j;
}
if(map[i][j]=='T')
{
dx=i;
dy=j;
}
}
flag=0;
f.x=sx;f.y=sy;
f.step=0;f.fx='n';
memset(num,99999,sizeof(num));
k1=0;
bfs();
if(flag==0)printf("-1\n");
if(flag==1){
int min=99999;
for(i=0;i<k1;i++)
if(num[k1]<min)min=num[i];
printf("%d\n",min);
}

}
return 0;
}




[解决办法]
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};

char map[101][101];
int visit[101][101][4];

int dx,dy,n,m;
struct node{
int x,y,step,fx;

};
queue<node>q;
node front,rear;

int bfs(int sx,int sy)
{
int tx,ty,tf,i,j,sstep;
front.x=sx;front.y=sy;front.step=0;front.fx=0;
while(!q.empty())q.pop();
q.push(front);
while(!q.empty())
{
front=q.front();
q.pop();
if(front.x==dx&&front.y==dy)
return front.step;
for(i=0;i<4;i++)
{
tx=front.x+dir[front.fx][0];
ty=front.y+dir[front.fx][1];
tf=front.fx;
if(tx>=0&&tx<n&&ty>=0&&ty<m&&map[tx][ty]!='#'&&!visit[tx][ty][tf])
{
sstep=front.step+1;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=front.fx;
visit[tx][ty][tf]=1;
q.push(rear);
}
//turn left
tx=front.x;
ty=front.y;
tf=(front.fx+1)%4;
if(!visit[tx][ty][tf])
{
sstep=front.step+1;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=tf;
visit[tx][ty][tf]=1;
q.push(rear);
}
//turn right
tx=front.x;
ty=front.y;
tf=(front.fx+3)%4;
if(!visit[tx][ty][tf])
{
sstep=front.step+1;
rear.x=tx;rear.y=ty;rear.step=sstep;rear.fx=tf;
visit[tx][ty][tf]=1;
q.push(rear);
}
}
}

return -1;
}

int main()
{
int t,i,j,sx,sy;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S'){
sx=i;
sy=j;
}
if(map[i][j]=='T'){
dx=i;
dy=j;
}
}

memset(visit,0,sizeof(visit));
visit[sx][sy][0]=1;
printf("%d\n",bfs(sx,sy));
}
return 0;
}