AOJ 1156 Twirling Robot http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156&lang=jp コストで昇順にしたpriority queueを使って、あとはdfs。ダイクストラ法ってやつなのかな

AOJ_1156.cpp

// start: 2013/07/11 3:12
// end: 2013/07/12 12:50
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <queue>

#define REP(i, n) for ( int i = 0; i < n; i++ )
#define INF INT_MAX

using namespace std;

class Rec {
public:
    int x;
    int y;
    int d;
    int cost;

    Rec( int xx, int yy, int dd, int s): x(xx), y(yy), d(dd), cost(s){}
};

bool operator< (const Rec& rec1, const Rec &rec2) {
    return rec1.cost > rec2.cost;
}
bool operator> (const Rec& rec1, const Rec &rec2) {
    return rec1.cost < rec2.cost;
}

int mx[4][4] = {{1, 0, -1, 0},
                {0, -1, 0, 1},
                {-1, 0, 1, 0},
                {0, 1, 0, -1}};
int my[4][4] = {{0, 1, 0, -1},
                {1, 0, -1, 0},
                {0, -1, 0, 1},
                {-1, 0, 1, 0}};

int main() {
    int w, h;

    while(cin >> w >> h, w||h) {
        // cout << w << " " << h << endl;
        priority_queue< Rec, vector<Rec>, less<vector<Rec>::value_type> > pq;

        vector< vector<int> > f(h, vector<int>(w));
        int closed[h][w][4];
        int COST[4];

        REP(y, h) REP(x, w) REP(i, 4) closed[y][x][i] = INF;

        REP(y, h) REP(x, w) cin >> f[y][x];
        REP(i, 4) cin >> COST[i];

        // dump(f);

        pq.push( Rec(0, 0, 0, 0));

        closed[0][0][0] = 0;

        while(!pq.empty()) {

            Rec tmp = pq.top(); pq.pop();
            int x = tmp.x,
                y = tmp.y,
                d = tmp.d,
                cost = tmp.cost,
                o = f[y][x];

            // printf("n:%d %d %d: %d\n", x, y, d, (0 <= x && x < w && 0 <= y && y < h));

            // ゴール
            if ( x == w-1 && y == h-1 ) {
                cout << cost << endl;
                break;
            }

            int nx = x + mx[d][o],
                ny = y + my[d][o],
                nd = (d+o) % 4;

            // マス目移動
            if ( o != 4 && 0 <= nx && nx < w && 0 <= ny && ny < h && cost < closed[ny][nx][nd] ) pq.push( Rec(nx, ny, nd, cost) );

            // 命令出す
            REP(i, 4) {
                if ( i == o ) continue; // マス目の命令と同じ

                int nx = x + mx[d][i],
                    ny = y + my[d][i],
                    nd = (d+i)%4;

                if ( 0 <= nx && nx < w && 0 <= ny && ny < h && cost+COST[i] < closed[ny][nx][nd] ) {
                    pq.push( Rec(nx, ny, nd, cost+COST[i]) );
                    closed[ny][nx][nd] = cost+COST[i];
                }
            }
        }
    }

    return 0;
}