はやし屋

競技プログラミングのメモ きたない

AOJ 1156: Twirling Robot

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

やるだけです

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdlib>
using namespace std;

#define fr first
#define sc second

typedef pair < int , int > Pi;
typedef pair <  Pi , Pi  > Pii;
typedef priority_queue < Pii , vector < Pii > , greater < Pii > > Que;

int w , h;

int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}

int st[111][111];
int c[111];

int solve(){
  Que que;
  que.push(Pii(Pi(0,0),Pi(0,0)));
  int vis[111][111][4] = {};
  while(!que.empty()){
    Pii pi = que.top();que.pop();
    int cost = pi.fr.fr, dir = pi.fr.sc;
    int    y = pi.sc.fr,   x = pi.sc.sc;
    if(y == h-1 && x == w-1)return cost;
    if(vis[y][x][dir]++)continue;
    for(int i = 0 ; i < 4 ; ++i){
      int ndir = (dir+i)%4 ;
      int ny    = y + dy[ndir] , nx = x + dx[ndir];
      if(!isover(ny,nx)){
	que.push(Pii(Pi(cost + (st[y][x] == i ? 0 : c[i] ), ndir),Pi(ny , nx)));
      }
    }
  }
  return -1;
}

int main(){
  while(cin >> w >> h && (w|h)){
    for(int i = 0 ; i < h ; ++i)
      for(int j = 0 ; j < w ; ++j)
	cin >> st[i][j];
    for(int i = 0 ; i < 4 ; ++i) cin >> c[i];
    
    cout << solve() << endl;
  }

}