Twirling Robot

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 }