fc2ブログ



Twirling Robot

2008.07.10 22:56  ACM/ICPC 2008



001 #include<iostream>
002 #include<queue>
003 using namespace std;
004 #define MAX 30
005 static const int STR = 0;
006 static const int RIGHT = 1;
007 static const int BACK = 2;
008 static const int LEFT = 3;
009 static const int HALT = 4;
010 static const int di[4] = {0, -1, 0, 1};
011 static const int dj[4] = {1, 0, -1, 0};
012
013 class Robot{
014 public:
015 int i, j, k, cost;
016 Robot(){}
017 Robot( int i, int j, int k, int cost ): i(i), j(j), k(k), cost(cost){}
018
019 void move( int com, int c ){
020 if ( com == LEFT ) k = (k+1)%4;
021 if ( com == RIGHT ) k = (k+3)%4;
022 if ( com == BACK ) k = (k+2)%4;
023 i += di[k]; j += dj[k];
024 cost += c;
025 }
026
027 bool operator < ( const Robot &s ) const{
028 return cost > s.cost;
029 }
030 };
031
032 int W, H, G[MAX][MAX], C[4];
033
034 bool valid( Robot r ){
035 return ( 0 <= r.i && 0 <= r.j && r.i < H && r.j < W );
036 }
037
038 int dijkstra(){
039 bool V[MAX][MAX][4];
040 for ( int i = 0; i < H; i++ ){
041 for ( int j = 0; j < W; j++ ) {
042 for ( int k = 0; k < 4; k++ ) V[i][j][k] = false;
043 }
044 }
045 priority_queue<Robot> PQ;
046 PQ.push(Robot(0, 0, 0, 0)); // i, j, direction, cost
047 Robot u, v; // current node, next node
048
049 while(!PQ.empty()){
050 u = PQ.top(); PQ.pop();
051 if ( u.i == H-1 && u.j == W-1 ) return u.cost;
052 V[u.i][u.j][u.k] = true;
053 v = u;
054 v.move(G[u.i][u.j], 0);
055 if ( G[u.i][u.j] != HALT && valid(v) && !V[v.i][v.j][v.k] ) PQ.push( v );
056 for ( int com = 0; com < 4; com++ ){
057 v = u;
058 v.move(com, C[com]);
059 if ( valid(v) && !V[v.i][v.j][v.k] ) PQ.push( v );
060 }
061 }
062 }
063
064 main(){
065 while( cin >> W >> H && ( W && H) ){
066 for ( int i = 0; i < H; i++ ){
067 for ( int j = 0; j < W; j++ ) cin >> G[i][j];
068 }
069 for ( int i = 0; i < 4; i++ ) cin >> C[i];
070 cout << dijkstra() << endl;
071 }
072 }


スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ