つーさのくーかん

書いてみた。条件式で何の面白みもないバグを出して1時間くらい。
つまんないバグが出なければ40分くらいで書けてたかな。
本番で書けたらよかった……。

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it!=(c).end(); ++it)
inline int toNode(int x, int y, int d, int w){return ((y*w)+x)*4 + d;}

struct EDGE {int from, to, weight;};
typedef vector<EDGE> EDGES;
typedef vector<EDGES> GRAPH;
inline bool operator > (const EDGE&a, const EDGE&b) { return a.weight>b.weight; }

int main()
{
    while(true)
    {
        // 読み込み
        int w,h; cin >> w >> h;
        if(w*h == 0) break;
        int map[w][h];
        REP(j,h) REP(i,w) cin >> map[i][j];
        int cost[4];
        REP(i,4) cin >> cost[i];

        const int dX[4] = { 1, 0, -1, 0, }; // 右下左上
        const int dY[4] = { 0, 1, 0, -1, };

        // グラフ作成
        GRAPH g;
        REP(y,h) REP(x,w) REP(d,4)
        {
            EDGES edgs;
            int cur = toNode(x,y,d,w);
            
            REP(cmd, 4)
            {
                int toD = (d+cmd)%4; // 新しい向き
                int toX = x+dX[toD], toY = y+dY[toD];
                if(toX<0 || toX>=w || toY<0 || toY>=h) continue;
                int next = toNode(toX, toY, toD, w);
                
                int weight = (map[x][y] == cmd) ? 0 : cost[cmd]; 
                edgs.push_back( (EDGE){cur,next,weight} );
            }
            g.push_back(edgs);
        }

        // ダイクストラ
        priority_queue<EDGE, vector<EDGE>, greater<EDGE> > q;
        q.push( (EDGE){-1, 0, 0} );
        vector<bool> visited(w*h*4);
        int goal = toNode(w-1, h-1, 0, w)/4;
        int ret;
        
        while( !q.empty() )
        {
            EDGE e = q.top(); q.pop();
            if( visited[e.to]) continue;
            visited[e.to] = true;
            if(e.to/4 == goal){ ret = e.weight; break; }
            FOR(it, g[e.to])
                if(!visited[it->to])
                    q.push((EDGE){it->from, it->to, it->weight + e.weight});
        }

        cout << ret << endl;
    }
    return 0;
}