1156: Twirling Robot

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156

g[現在の方向][Y][X]:=最短距離
でダイクストラ。

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define INF (1<<29)
#define Cost first.first
#define Dir first.second
#define X second.first
#define Y second.second

using namespace std;

typedef pair<int,int> p2;
typedef pair<p2,p2> p4;

int w,h,g[4][31][31],s[31][31],c[4];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int dijkstra(){

  priority_queue<p4,vector<p4>, greater<p4> >que;

  fill(*g[0],*g[4],INF);
  g[0][0][0]=0;
  
  p4 st = p4(p2(0,0),p2(0,0));
  que.push(st);

  bool fg=false;

  while(!que.empty()){
    p4 now = que.top();
    que.pop();

    if(now.Y==h-1 && now.X==w-1)return now.Cost;    
    if(g[now.Dir][now.Y][now.X]<=now.Cost && fg)continue;
    fg=true;
    g[now.Dir][now.Y][now.X]=now.Cost;
    
    rep(d,4){
      p4 next;
      next.Dir=(now.Dir+d)%4;
      next.X=now.X+dx[next.Dir],next.Y=now.Y+dy[next.Dir];
      if(0<=next.X && next.X<w && 0<=next.Y && next.Y<h){
	next.Cost=now.Cost+c[d]*(s[now.Y][now.X]!=d);
	que.push(next);
      }
    }
  }
  return -1;
}

int main(void){
  
  while(cin >> w >> h,w|h){
    rep(i,h)rep(j,w)cin >> s[i][j];
    rep(i,4)cin >> c[i];
    cout << dijkstra() << endl;
  }
  return 0;
}