aoj 1156 - Twirling Robot

問題

問題概要

盤面に命令が書いてある。命令通りに行動すればコストは0。命令以外の行動をすれば、コストは指定された通りのコストがかかる。スタートからゴールまで行くのにかかる最短コストを求めよ。

解法

拡張ダイクストラで解いた。頂点の状態に番号だけでなく、その頂点にどの方向から来たかを持たせる。こうすることで、dist[t][y][x] :=　現在の座標が(x, y)で来た方向がtの時の最短コスト　として、ダイクストラで値を更新していくことができる。

ミス

初期化ミスでだいぶ悩んだ。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <tuple>
using namespace std;
typedef long long ll;
typedef tuple<int, int, pair<int, int> > tup;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
int w, h;
int s[32][32];
int c[6];
//dist[t][y][x] :=　現在の座標が(x, y)で来た方向がtの時の最短コスト
int dist[6][32][32];

void dijkstra(void){
    rep(i, 6)rep(j, 32)rep(k, 32){
        dist[i][j][k] = INF;
    }

    priority_queue<tup, vector<tup>, greater<tup> >  q;//コスト　どの方向から来たか 現在の座標
    dist[1][0][0] = 0;
    q.push(make_tuple(0, 1, make_pair(0, 0)));

    while(!q.empty()){
        int cost, v;
        pair<int, int> p;
        tie(cost, v, p) = q.top(); q.pop();
        int y = p.first, x = p.second;
        if(dist[v][y][x] < cost) continue;

        for (int i = 0; i < 4; ++i){//直進右折反転左折の順に試す
            int nextv = (v + i) % 4;
                //ここからへんがおかしい
            int ny = y + dy[nextv], nx = x + dx[nextv];
            if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
            if(i == s[y][x]){//指示通り
                if(cost < dist[nextv][ny][nx]){
                    dist[nextv][ny][nx] = cost;
                    q.push(make_tuple(dist[nextv][ny][nx], nextv, make_pair(ny, nx)));
                }
            }else{
                if(cost + c[i] < dist[nextv][ny][nx]){
                    dist[nextv][ny][nx] = cost + c[i];
                    q.push(make_tuple(dist[nextv][ny][nx], nextv, make_pair(ny, nx)));
                }
            }
        }
    }
}

int main(void){
    while(1){
        cin >> w >> h;
        if(w == 0 && h == 0) return 0;
        rep(i, h)rep(j, w) cin >> s[i][j];
        rep(i, 4){
            cin >> c[i];
        }

        dijkstra();

        int ans = INF;
        for (int i = 0; i < 4; ++i){
            ans = min(ans, dist[i][h - 1][w - 1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}