AOJ_0050 Cliff Climbingをclass＋priority_queueで解いてみた。 これなら最初にゴールに至った経路＝最小コストなので楽ちん。

AOJ_1150_pq.cpp

// start: 21:57
// AC: 00:12
#include <cstdio>
#include <climits>
#include <iostream>
#include <vector>
#include <queue>

#define REP(i, n) for ( int i = 0; i < n; i++ )
#define INF INT_MAX

using namespace std;

typedef pair<int, int> xy;

void dump(vector< vector<char> > &f, int x = -1, int y = -1, int l = -1) {
    REP(i, f.size()) {
        REP(j, f[i].size()) {
            if ( i == y && j == x ) {
                if ( l == 0 )
                    cout << "R";
                else
                    cout << "L";
            }
            else
                cout << f[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

class Climb {
public:
    int cost;
    int leg;
    xy foot;
    Climb(xy f, int l, int c): foot(f), leg(l), cost(c){}
};

bool operator< (const Climb& cl1, const Climb &cl2) {
    return cl1.cost > cl2.cost;
}
bool operator> (const Climb& cl1, const Climb &cl2) {
    return cl1.cost < cl2.cost;
}

// 左足のときに置ける右足
int mx[] = {1, 1, 2, 1, 2, 3, 1, 2, 1},
    my[] = {2, 1, 1, 0, 0, 0, -1, -1, -2};

int main() {
    int w, h;

    while(cin >> w >> h, w||h) {
        priority_queue< Climb, vector<Climb>, less<vector<Climb>::value_type> > pq;

        int closed[h][w][2];
        // vector< queue<xy> > foot(2);   // 0:右 1:左
        // queue<int> cost, leg;
        vector< vector<char> > f(h);
        vector< xy > start;

        REP(i, h) REP(j, w) REP(k, 2) closed[i][j][k] = 0;

        REP(i, h) {
            REP(j, w) {
                char tmp;
                cin >> tmp;
                f[i].push_back(tmp);
                if ( f[i][j] == 'S' ) {
                    start.push_back( make_pair(j, i) );
                }
            }
        }

        // スタート地点＋左右を初期値としてpush
        REP(i, start.size()) {
            // 0:右, 1:左
            pq.push( Climb( make_pair(start[i].first, start[i].second), 0, 0) );
            pq.push( Climb( make_pair(start[i].first, start[i].second), 1, 0) );
        }

        int min = INF;
        while(!pq.empty()) {
            Climb climb = pq.top(); pq.pop();

            int c = climb.cost;
            int l = climb.leg;

            xy ft = climb.foot;
            int x = ft.first;
            int y = ft.second;

            // printf("f:%d, x:%d, y:%d, xy:%c\n", l, x, y, f[y][x]);
            // dump(f, x, y, l);
            if ( f[y][x] == 'T' ) {
                min = c;
                break;
            }

            REP(i, 9) {
                int dir = l == 0 ? -1: 1,
                    nx = x + mx[i] * dir,
                    ny = y + my[i],
                    nl = !l;

                if ( !(0 <= nx && nx < w && 0 <= ny && ny < h) ) continue;
                if ( f[ny][nx] == 'X' || f[ny][nx] == 'S' ) continue;   // バグ出るかも

                int nc;
                if ( ((int)f[ny][nx] - 48) > 9 )
                    nc = c + 1;
                else
                    nc = c + ((int)f[ny][nx] - 48);

                if ( closed[ny][nx][nl] != 0 && closed[ny][nx][nl] < nc ) continue;

                pq.push( Climb( make_pair(nx, ny), nl, nc) );
                closed[ny][nx][nl] = nc;

            }
        }

        if ( min == INF )
            cout << -1 << endl;
        else
            cout << (min-1) << endl;
    }
    return 0;
}