AOJ2425 全探索お姉さんの休日

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2425
　六角形のタイルの上を移動するとき、|x * y * t(経過時間)|% 6により定められる方向に違反する回数をなるべく少なくして辿り着きたい、という問題。
　まず真っ先に状態数は頂点数×(時間%6)通りしかないからメモ化再帰でいける、と思ったのですがダメでしたね。同じところを何回も通れるようにすると無限ループを仕込んでしまうし、一回しか通れないようにすると最適でないルートを選んだときの値で固定されてしまいます。そこで、priority_queueなどを使って、最短であることが確定している状態から埋めていくことにします。何個か状態の候補があれば、その中で一番コストが低いものは最短だと確定しているはずだ、という。要するに拡張ダイクストラ法で解きます。

const int dx[7] = {0, 1, 1, 0, -1, -1, 0}, dy[2][7] = {{1, 0, -1, -1, -1, 0, 0}, {1, 1, 0, -1, 0, 1, 0}};
int sx, sy, gx, gy, ux, uy, lx, ly;
bool cant_in[201][201];
int dist[201][201][6];
struct Node{
    int x, y, tmod;
    int cost;//sx, syから何回の命令違反で来られるか
    Node(int x, int y, int tmod, int cost)
         :x(x), y(y), tmod(tmod), cost(cost) {}
    bool operator>(const Node& N) const {
        return cost > N.cost;
    }
};
int solve(){
    rep(i, 201) rep(j, 201) rep(k, 6) dist[i][j][k] = INF;
    priority_queue<Node, vector<Node>, greater<Node> > que;
    dist[sy][sx][0] = 0;
    que.push(Node(sx, sy, 0, 0));
    while(!que.empty()){
        Node now = que.top(); que.pop();
        if(dist[now.y][now.x][now.tmod] < now.cost) continue;
        int xmod = now.x % 2, nt = (now.tmod + 1) % 6;
        int cmdir = abs((now.x - 100) * (now.y - 100) * now.tmod) % 6;
        rep(i, 7){
            int nx = now.x + dx[i], ny = now.y + dy[xmod][i];
            if(nx < lx || ny < ly || ux < nx || uy < ny) continue;
            if(cant_in[ny][nx]) continue;
            int plus = 1;
            if(i == cmdir) plus = 0;
            if(dist[ny][nx][nt] > now.cost + plus){
                dist[ny][nx][nt] = now.cost + plus;
                que.push(Node(nx, ny, nt, dist[ny][nx][nt]));
            }
        }
    }
    int res = INF;
    rep(i, 6) res = min(dist[gy][gx][i], res);
    return res == INF ? -1 : res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    memset(cant_in, 0, sizeof(cant_in));
    cin >> sx >> sy >> gx >> gy;
    sx += 100; sy += 100; gx += 100; gy += 100;
    int n, _x, _y; cin >> n;
    rep(i, n){
        cin >> _x >> _y;
        cant_in[_y + 100][_x + 100] = true;
    }
    cin >> _x >> _y;
    ux = 100 + _x; lx = 100 - _x; uy = 100 + _y; ly = 100 - _y;
    cout << solve() << endl;
    return 0;
}

　遷移の埋め込みはけっこう意地悪だと思いますが、解法パートはわりと面白いと思いました。