AOJ1150 崖登り

見た感じ得意分野の経路探索系だったのでやった。
見たとおりそのまま実装したらこうなった。

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef pair< int , int > P;
typedef pair< pair< int , P > , pair< P , bool > > PP;
//コスト,左座標,右座標,次どっちの足？(true:左,false:右)
#define fr first
#define sc second
#define MAX_W 30
#define MAX_H 60
#define mp(a,b) make_pair(a,b)
 
const int dx[]={1,1,1,1,1,2,2,2,3},dy[]={2,1,0,-1,-2,1,0,-1,0};
int w,h;
char mas[MAX_H][MAX_W];
 
bool over(int nx,int ny){
  return nx < 0 || nx >= w || ny < 0 || ny >= h;
}
 
int bfs(vector<P>& st){
  map< pair< pair< P , P > , bool > , bool > used;
  priority_queue< PP , vector<PP> , greater<PP> > que;
  for(int i = 0 ; i < st.size() ; i++ ){
    que.push(PP(mp(0,st[i]),mp(P(-1,-1),false)));
    que.push(PP(mp(0,P(-1,-1)),mp(st[i],true)));
  }
  while(!que.empty()){
    PP p = que.top();
    que.pop();
    if(used[mp(mp(p.fr.sc,p.sc.fr),p.sc.sc)]++) continue;
    if(mas[p.fr.sc.fr][p.fr.sc.sc] == '0') return p.fr.fr;
    if(mas[p.sc.fr.fr][p.sc.fr.sc] == '0') return p.fr.fr;
    for(int i = 0 ; i < 9 ; i++ ){
      if(p.sc.sc){ // 左足を動かす
        int ny = p.sc.fr.fr + dy[i] , nx = p.sc.fr.sc - dx[i];
        if(over(nx,ny) || mas[ny][nx] == 'X') continue;
        que.push(PP(mp(p.fr.fr+(mas[ny][nx]-'0'),P(ny,nx)),mp(p.sc.fr,false)));
      }else{ //右足を動かす
        int ny = p.fr.sc.fr + dy[i] , nx = p.fr.sc.sc + dx[i]; // p.sc.fr.sc + dx[i]
        if(over(nx,ny) || mas[ny][nx] == 'X') continue;
        que.push(PP(mp(p.fr.fr+(mas[ny][nx]-'0'),p.fr.sc),mp(P(ny,nx),true)));
      }
    }
  }
  return -1;
}
 
int main(){
  while(cin >> w >> h , w){
    vector<P> st;
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
        if(mas[i][j] == 'S') st.push_back(P(i,j));
        if(mas[i][j] == 'T') mas[i][j] = '0';
      }
    }
    cout << bfs(st) << endl;
  }
}

ダイクストラバグったじゃんと思ったら、入力のミスだったという経緯があって、
精神的に逝きました。(小並感)。59,60行目がmas[i][w]になっていたというクソザコ。
で、解き終わったあと、どっちかの足だけでいいじゃんということに気付いて絶望。
気分が悪いので解き直し。

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef pair< int , int > P;
typedef pair< pair< int , P > , bool > PP;
//コスト,座標,次どっちの足？(true:左,false:右)
#define fr first
#define sc second
#define MAX_W 30
#define MAX_H 60
#define mp(a,b) make_pair(a,b)
 
const int dx[]={1,1,1,1,1,2,2,2,3},dy[]={2,1,0,-1,-2,1,0,-1,0};
int w,h;
char mas[MAX_H][MAX_W];
 
bool over(int nx,int ny){
  return nx < 0 || nx >= w || ny < 0 || ny >= h;
}
 
int bfs(vector<P>& st){
  bool used[MAX_H][MAX_W][2] = {};
  priority_queue< PP , vector<PP> , greater<PP> > que;
  for(int i = 0 ; i < st.size() ; i++ ){
    que.push(PP(mp(0,st[i]),false));
    que.push(PP(mp(0,st[i]),true));
  }
  while(!que.empty()){
    PP p = que.top();
    que.pop();
    if(used[p.fr.sc.fr][p.fr.sc.sc][p.sc]++) continue;
    if(mas[p.fr.sc.fr][p.fr.sc.sc] == '0') return p.fr.fr;
    for(int i = 0 ; i < 9 ; i++ ){
      int ny = p.fr.sc.fr + dy[i] , nx = p.fr.sc.sc + (p.sc ? dx[i] : -dx[i]);
      if(over(nx,ny) || mas[ny][nx] == 'X') continue;
      que.push(PP(mp(p.fr.fr+(mas[ny][nx]-'0'),P(ny,nx)),!p.sc));
    }
  }
  return -1;
}
 
int main(){
  while(cin >> w >> h , w){
    vector<P> st;
    for(int i = 0 ; i < h ; i++ ){
      for(int j = 0 ; j < w ; j++ ){
        cin >> mas[i][j];
        if(mas[i][j] == 'S') st.push_back(P(i,j));
        if(mas[i][j] == 'T') mas[i][j] = '0';
      }
    }
    cout << bfs(st) << endl;
  }
}

疲れた。