ICPC 国内予選2008D ちょろちょろロボット AOJ 1156

基本的にやることはICPC 国内予選2007D 崖登り AOJ1150 - intさわだんのBlack Historyとおんなじ
幅優先探索でゴリ押す

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
int INF = 1000000;

int ban[35][35],w,h,c[4],dp[35][35][4];
int dj[4][4] = {{0,1,0,-1},
              {1,0,-1,0},
              {0,-1,0,1},
              {-1,0,1,0} };
int di[4][4] = {{-1,0,1,0},
              {0,1,0,-1},
              {1,0,-1,0},
              {0,-1,0,1}};

int next_direction(int i,int j,int ni,int nj){
    if(i == ni){
        if(j > nj){
            return 3;
        }else{
            return 1;
        }
    }else{
        if(i > ni){
            return 0;
        }else{
            return 2;
        }
    }
}

int main(){
    while(true){
        cin >> w >> h;
        if(w + h == 0)break;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= w;j++){
                cin >> ban[i][j];
                for(int k = 0;k < 4;k++) dp[i][j][k] = INF;
            }
        }
        for(int i = 0;i < 4;i++){
            cin >> c[i];
        }
        queue<T> que;
        dp[1][1][1] = 0;
        que.push(make_tuple(1,1,1,0));
        while(!que.empty()){
            T t = que.front(); que.pop();
            int i = get<0>(t),j = get<1>(t),d = get<2>(t),cost = get<3>(t);
     //       cout << "i:" << i << ", j:" << j << ", d:" << d << ", cost:" << cost <<endl;
            if(dp[i][j][d] != cost || (i == h && j == w)) continue;
            for(int k = 0;k < 4;k++){
                int ni = i + di[d][k],nj = j + dj[d][k];
                int nd = next_direction(i,j,ni,nj);
                if(ni <= 0 || ni > h || nj <= 0 || nj > w)continue;
                int same_d = 0;
                if(k == ban[i][j]) same_d = c[k];
                if(dp[ni][nj][nd] > cost + c[k] - same_d){
                    dp[ni][nj][nd] = cost + c[k] - same_d;
                    que.push(make_tuple(ni,nj,nd,dp[ni][nj][nd]));
                }
            }
        }
        int ans = INF;
        for(int k = 0;k < 4;k++){
            ans = min(ans,dp[h][w][k]);
        }
        cout << ans << endl;
    }
}