Cliff Climbing
2007.07.16 01:31 ACM/ICPC 2007
[問題] ACM/ICPC 国内予選2007: Problem D
[解説]
知識問題。知ってる人はラッキー☆な問題です。
ダイクストラのアルゴリズム(順位優先探索)で解きます。
この問題では、探索の空間が
足 f で崖 (i, j) にいる状態
となります。この空間においてダイクストラのアルゴリズムによって最短距離を求めます。
ダイクストラのアルゴリズムの原理を良く理解し、かつ何も見ないで実装できる力が必要ですね。
[解説]
知識問題。知ってる人はラッキー☆な問題です。
ダイクストラのアルゴリズム(順位優先探索)で解きます。
この問題では、探索の空間が
足 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 }
スポンサーサイト
| コメント(2) | トラックバック(0) | ↑ページトップ |