题意：
给一张二维地图，求从标有‘S’到标有‘T’之间的最短路，特殊的地方在于每次走的方向要左右交替。
思路：
spfa即可，关键在dis数组的定义，dis[0][x][y]和dis[1][x][y]分别表示两只脚在x,y点上时的最小值，距离g函数可在运行时确定，不用预处理，否则很耗内存。
代码：
//poj 3328
//sepNINE
#include <iostream>
#include <queue>
using namespace std;
const int maxN=100;
int w,h;
int dis[maxN][maxN][2];
int inq[maxN][maxN][2];
char cliff[maxN][maxN];
struct Node
{int x,y,state;
};
queue<Node> Q;
void spfa()
{while(!Q.empty()){Node top=Q.front();Q.pop();int nx=top.x,ny=top.y,ns=top.state;inq[nx][ny][ns]=0; if(ns==0){int i,j,time;for(i=nx-2;i<=nx+2;++i)for(j=ny+1;j<=ny+3;++j)if(i>=1&&i<=h&&j>=1&&j<=w&&abs(i-nx)+abs(j-ny)<=3&&cliff[i][j]!='X'){if(cliff[i][j]=='T'||cliff[i][j]=='S')time=0;else time=cliff[i][j]-'0';if(dis[i][j][1]>dis[nx][ny][0]+time){dis[i][j][1]=dis[nx][ny][0]+time;if(inq[i][j][1]==0){inq[i][j][1]=1;Node a;a.x=i;a.y=j;a.state=1;Q.push(a);}}}}else{int i,j,time;for(i=nx-2;i<=nx+2;++i)for(j=ny-1;j>=ny-3;--j)if(i>=1&&i<=h&&j>=1&&j<=w&&abs(i-nx)+abs(j-ny)<=3&&cliff[i][j]!='X'){if(cliff[i][j]=='T'||cliff[i][j]=='S')time=0;else time=cliff[i][j]-'0';if(dis[i][j][0]>dis[nx][ny][1]+time){dis[i][j][0]=dis[nx][ny][1]+time;if(inq[i][j][0]==0){inq[i][j][0]=1;Node a;a.x=i;a.y=j;a.state=0;Q.push(a);}}} }}
}int main()
{while(scanf("%d%d",&w,&h)==2&&!(h==0&&w==0)){int i,j,k,t,r,c;for(i=1;i<=h;++i)for(j=1;j<=w;++j)cin>>cliff[i][j];for(j=1;j<=h;++j)for(k=1;k<=w;++k){dis[j][k][0]=INT_MAX;dis[j][k][1]=INT_MAX;}int ans=INT_MAX;memset(inq,0,sizeof(inq));for(r=1;r<=h;++r)for(i=1;i<=w;++i)if(cliff[r][i]=='S'){dis[r][i][0]=0;dis[r][i][1]=0; inq[r][i][0]=1;inq[r][i][1]=1;Node a;a.x=r;a.y=i,a.state=0;Q.push(a);a.state=1;Q.push(a);}spfa(); for(c=1;c<=h;++c)for(k=1;k<=w;++k)if(cliff[c][k]=='T'){ans=min(ans,dis[c][k][0]);ans=min(ans,dis[c][k][1]);}if(ans==INT_MAX)printf("-1\n");elseprintf("%d\n",ans);}
}