Cliff Climbing

[問題] ACM/ICPC 国内予選2007: Problem D
[解説]
知識問題。知ってる人はラッキー☆な問題です。
ダイクストラのアルゴリズム（順位優先探索）で解きます。
この問題では、探索の空間が

足 f で崖 (i, j) にいる状態

となります。この空間においてダイクストラのアルゴリズムによって最短距離を求めます。

ダイクストラのアルゴリズムの原理を良く理解し、かつ何も見ないで実装できる力が必要ですね。

001 #include<iostream>
002 #include<queue>
003 using namespace std;
004 #define HMAX 60
005 #define WMAX 30
006 #define LEFT 0
007 #define RIGHT 1
008 #define INFTY (1<<21)
009 
010 class State{
011     public:
012     int i, j, f, c; // i, j, foot, cost
013     State(){}
014     State( int i, int j, int f, int c ): i(i), j(j), f(f), c(c){}
015     
016     bool operator < ( const State &s ) const{
017         return c > s.c;
018     }
019 };
020 
021 int H, W;
022 char C[HMAX][WMAX]; //cliff
023 priority_queue<State> PQ;
024 int D[HMAX][WMAX][2];
025 bool visited[HMAX][WMAX][2];
026 
027 bool isOutside( int i, int j ){
028     return ( i < 0 || j < 0 || H <= i || W <= j);
029 }
030 
031 int dijkstra(){
032     static const int di[2][9] = {{-2, -1, -1, 0, 0, 0, 1, 1, 2},
033                                  {-2, -1, -1, 0, 0, 0, 1, 1, 2}};
034     static const int dj[2][9] = {{-1, -2, -1, -3, -2, -1, -2, -1, -1},
035                                  {1, 1, 2, 1, 2, 3, 1, 2, 1}};
036     State u, v;
037     int ni, nj, nf;
038     
039     while ( !PQ.empty() ){
040         u = PQ.top(); PQ.pop();
041         if ( C[u.i][u.j] == 'T' ) return D[u.i][u.j][u.f];
042         visited[u.i][u.j][u.f] = true;
043         
044         for ( int r = 0; r < 9; r++ ){
045             nf = (u.f + 1)%2;
046             ni = u.i + di[nf][r]; nj = u.j + dj[nf][r];
047             if ( isOutside( ni, nj ) ||
048             C[ni][nj] == 'X' || visited[ni][nj][nf] ) continue;
049             int cost = D[u.i][u.j][u.f] + ((C[ni][nj]=='T')?0:(C[ni][nj]-'0'));
050             if ( cost < D[ni][nj][nf] ){
051                 D[ni][nj][nf] = cost;
052                 PQ.push( State(ni, nj, nf, cost) );
053             }
054         }
055     }
056     
057     return -1;
058 }
059 
060 bool initialize(){
061     cin >> W >> H;
062     if ( W == 0 && H == 0 ) return false;
063     PQ = priority_queue<State>();
064     for ( int i = 0; i < H; i++ ){
065         for ( int j = 0; j < W; j++ ){
066             cin >> C[i][j];
067             if ( C[i][j] == 'S' ){
068                 PQ.push( State( i, j, LEFT, 0) );
069                 PQ.push( State( i, j, RIGHT, 0) );
070                 D[i][j][LEFT] = D[i][j][RIGHT] = 0;
071             } else {
072                 D[i][j][LEFT] = D[i][j][RIGHT] = INFTY;
073             }
074             visited[i][j][0] = visited[i][j][1] = false;
075         }
076     }
077     return true;
078 }
079 
080 main(){
081     while ( initialize() ) cout << dijkstra() << endl;
082 }