ICPC 国内予選2007D 崖登り AOJ1150

解法：幅優先探索。右足でたどり着いたときの最小時間と左足の時の最小時間を分けて考える。

この手の問題は得意なので秒で通した。（実際は分で通した。

tupleとqueueのコンボが最強であることを知った。（自分が現役だったころはtupleなかった気がする。最近でてきた？？）

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
int INF = 1000000;


int dx[2][9]= { { 1,1,1,1,1,2,2,2,3},
                {-1,-1,-1,-1,-1,-2,-2,-2,-3}};
int dy[2][9] = {{ 2,1,0,-1,-2,1,0,-1,0},
                {2,1,0,-1,-2,1,0,-1,0}};


int w,h;
char cliff[65][35];
int dp[65][35][2];

bool check(int i,int j){
    if(i < 0 || i >= h || j < 0 || j >= w) return false;
    if(cliff[i][j] == 'X')return false;
    return true;
}

int main(){
    while(true){
        cin >> w >> h;
        if(w + h == 0)break;
        queue<T> que;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                dp[i][j][0] = INF;
                dp[i][j][1] = INF;
                cin >> cliff[i][j];
                if(cliff[i][j] == 'S'){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                    que.push(make_tuple(i,j,0,0));
                    que.push(make_tuple(i,j,1,0));
                    cliff[i][j] = '0';
                }
            }
        }
        while(!que.empty()){
            T t = que.front(); que.pop();
            int y = get<0>(t),x = get<1>(t),lr = get<2>(t),m = get<3>(t);
            if(dp[y][x][lr] != m)continue;
            for(int k = 0;k < 9;k++){
                int i = y + dy[lr][k],j = x + dx[lr][k];
                if(check(i,j) == false)continue;
                if(dp[i][j][(lr+1)%2] > m + (int) (cliff[y][x] - '0') ){
                    dp[i][j][(lr+1)%2] = m +  (int) (cliff[y][x] - '0') ;
                    if(cliff[i][j] != 'T'){
                        que.push(make_tuple(i,j,(lr+1)%2,dp[i][j][(lr+1)%2]));
                    }
                }
            }
        }
        int ans = INF;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                for(int k = 0;k < 2;k++){
                    if(cliff[i][j] == 'T') ans = min(ans,dp[i][j][k]);
                }
            }
        }
        if(ans == INF)ans = -1;
        cout << ans << endl;
    }
}