AOJ_1150 Cliff Climbing http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150 複数のキューを使っているので、プライオリティキューを利用できなかった。

AOJ_1150.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++ )

using namespace std;

typedef pair<int, int> xy;

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

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;
}

int main() {
    int w, h;

    while(cin >> w >> h, w||h) {
        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()) {
            int l = 0;
            leg.push(l);
            foot[l].push( make_pair(start[i].first, start[i].second) );
            cost.push(0);

            l = 1;
            leg.push(l);
            foot[l].push( make_pair(start[i].first, start[i].second) );
            cost.push(0);
        }

        int min = INT_MAX;
        while(!cost.empty()) {
            int c = cost.front(); cost.pop();
            int l = leg.front(); leg.pop();
            xy ft = foot[l].front(); foot[l].pop();
            int x = ft.first, 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' && c < min ) {
                min = c;
                continue;
            }

            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;

                cost.push(nc);
                leg.push(nl);   // 逆足
                foot[nl].push( make_pair(nx, ny) );
                closed[ny][nx][nl] = nc;

            }
        }

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