题目描述：

从地图最下一行的S出发，到最上一行的T，S，T任去一个现存的即可。

同时每个点有左右脚之分，左脚在这个点，那么下一步只能迈右脚向右侧指定的9个点走，同理右脚在一个点只能用左脚走左侧指定的9个点。

问到T的最短路。

解题报告：

每个点看成2个点（左右脚各一个），一共是60*30*2个点。

每个点可到达的点也记下来，算作一条边。

这样就转化成求最短路了。spfa解之。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define size 2000
struct edge{int to, next, val;}e[10000000];
int v[size][2], cnt, d[size][2], que[size * 50][2];
bool vst[size][2];
void insert(int from, int id, int to, int val)
{
    e[cnt].to = to; e[cnt].val = val;
    e[cnt].next = v[from][id]; v[from][id] = cnt++;
}
int h, w;
void spfa(int sta, int n, int d[][2])
{
    for(int i = 0; i < n; i++) d[i][0] = d[i][1] = -1, vst[i][0] = vst[i][1] = 0;
    vst[sta][0] = vst[sta][1] = 1;int head = 0, tail = 0;
    que[tail][0] = sta; que[tail++][1] = 0;
    que[tail][0] = sta; que[tail++][1] = 1;
    d[sta][0] = d[sta][1] = 0;
    while(head < tail)
    {
        int a1 = que[head][0]; int a2 = que[head++][1];
        vst[a1][a2] = 0;
        for(int i = v[a1][a2]; i != -1; i = e[i].next)
            if (d[e[i].to][a2 ^ 1] == -1 || d[a1][a2] + e[i].val < d[e[i].to][a2 ^ 1])
            {
                d[e[i].to][a2 ^ 1] = d[a1][a2] + e[i].val;
                if (!vst[e[i].to][a2 ^ 1])
                {
                    vst[e[i].to][a2 ^ 1] = 1;
                    que[tail][0] = e[i].to; que[tail++][1] = (a2 ^ 1);
                }
            }
    }
}
char g[80][80], str[3];
int move[2][9][2] =
{{0, 1, 0, 2, 0, 3, 1, 1, 1, 2, 2, 1, -1, 1, -1, 2, -2, 1},
 {0, -1, 0, -2, 0, -3, 1, -1, 1, -2, 2, -1, -1, -1, -1, -2, -2, -1}};
void judge(int id, int a, int b)
{
    for(int i = 0; i < 9; i++)
    {
        int tmpa = a + move[id][i][0], tmpb = b + move[id][i][1];
        if (tmpa >= 0 && tmpa < h && tmpb >= 0 && tmpb < w && g[tmpa][tmpb] != 'X')
        {
            if (g[tmpa][tmpb] >= '0' && g[tmpa][tmpb] <= '9') insert(a * w + b, id, tmpa * w + tmpb, g[tmpa][tmpb] - '0');
            else  insert(a * w + b, id, tmpa * w + tmpb, 0);
        }
    }
}
int main()
{
    while(scanf("%d%d", &w, &h) && (w || h))
    {
        for(int i = 0; i < h * w; i++) v[i][0] = v[i][1] = -1;
        cnt = 0;
        for(int i = 0; i < h; i++)
            for(int j = 0; j < w; j++)
                scanf("%s", str), g[i][j] = str[0];
        for(int i = 0; i < h; i++)
            for(int j = 0; j < w; j++)
                if (g[i][j] != 'X') judge(0, i, j), judge(1, i, j);
        int ans = 0x7fffffff;
        for(int i = 0; i < w; i++)
            if (g[h - 1][i] == 'S')
            {
                spfa((h - 1) * w + i, h * w, d);
                for(int j = 0; j < w; j++)
                    if (g[0][j] == 'T')
                    {
                        if (d[j][0] != -1) ans = min(ans, d[j][0]);
                        if (d[j][1] != -1) ans = min(ans, d[j][1]);
                    }
            }
        if (ans == 0x7fffffff) printf("-1\n");
        else printf("%d\n", ans);
    }
}