zoj 3103 Cliff Climbing（spfa ）(二)
eam"
#include"algorithm"
using namespace std;
#define N 105
const int inf=(int)1e10;
int w,h,ans;
char e[N][N];
int mark1[N][N],mark2[N][N]; //记录左右脚走到某一点时的最小时间
struct node
{
int x,y,t,f; //f记录走到该点是左脚（-1）还是右脚（1）
};
bool judge(int x,int y) //判断该点是否能走
{
if(x>=0&&x
=0&&y
q; node cur,next; cur.t=0; for(i=0;i
=mark1[u][v]) continue; next.x=u; next.y=v; mark1[u][v]=next.t; q.push(next); } } } } } if(cur.f==-1) { next.f=1; for(i=-2;i<=2;i++) { for(j=1;j<=3;j++) { if(abs(i)+abs(j)<=3) { u=x+i;v=y+j; if(judge(u,v)) { if(e[u][v]=='T') { ans=min(ans,cur.t); //printf("%d\n",ans); continue; } next.t=cur.t+e[u][v]-'0'; if(next.t>=mark2[u][v]) continue; next.x=u; next.y=v; mark2[u][v]=next.t; q.push(next); } } } } } } } int main() { int i,j; while(scanf("%d%d",&w,&h),w||h) { for(i=0;i
>e[i][j]; mark1[i][j]=mark2[i][j]=inf; } } ans=inf; spfa(); if(ans>=inf) printf("-1\n"); else printf("%d\n",ans); } return 0; }