Aizu Online Judge 2425 - A Holiday of Miss Brute Force

問題

Pokemon Goリリース当日の記事です。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2425

解法

x座標、y座標、を6で割った余りを状態として、命令回数を最小化する拡張Dijkstraです。

ソースコード

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct State {
    int t_mod6, x, y, cost;

    State(int t_mod6, int x, int y, int cost) :
        t_mod6(t_mod6), x(x), y(y), cost(cost) { }

    bool operator>(const State& s) const {
        return cost > s.cost;
    }
};

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

const int kINF = 1 << 28;
const int kMAX_ABS_X = 200;
const int kMAX_ABS_Y = 200;
const int kCENTER_X = kMAX_ABS_X;
const int kCENTER_Y = kMAX_ABS_Y;

int tile[kMAX_ABS_X * 2][kMAX_ABS_X * 2];
int cost[6][kMAX_ABS_X * 2][kMAX_ABS_Y * 2];

int sx, sy, gx, gy, n, lx, ly;

int Get(int arr[][kMAX_ABS_Y * 2], int x, int y) {
    return arr[kCENTER_X + x][kCENTER_Y + y];
}

void Set(int arr[][kMAX_ABS_Y * 2], int x, int y, int val) {
    arr[kCENTER_X + x][kCENTER_Y + y] = val;
}

bool InTile(int x, int y) {
    return abs(x) <= lx && abs(y) <= ly;
}

// (t mod 6, x, y)を状態として, 命令回数を最小化する拡張Dijkstra
void Dijkstra() {
    // 初期化(ここだけ実際の座標を用いる)
    for (int t_mod6 = 0; t_mod6 < 6; t_mod6++)
        for (int x = 0; x < kMAX_ABS_X * 2; x++)
            for (int y = 0; y < kMAX_ABS_Y * 2; y++)
                cost[t_mod6][x][y] = kINF;

    priority_queue<State, vector<State>, greater<State>> que;
    que.push(State(0, sx, sy, 0));
    Set(cost[0], sx, sy, 0);
    while (!que.empty()) {
        State s = que.top(); que.pop();
        if (s.cost > Get(cost[s.t_mod6], s.x, s.y)) continue;

        for (int dir = 0; dir < 6; dir++) {
            int nt_mod6 = (s.t_mod6 + 1) % 6,
                nx = s.x + dx[abs(s.x) % 2][dir],
                ny = s.y + dy[abs(s.x) % 2][dir],
                ncost = (dir == abs(s.x * s.y * s.t_mod6) % 6) ? s.cost : s.cost + 1;
            // 移動できるのであれば
            if (InTile(nx, ny) && Get(tile, nx, ny) >= 0 &&
                    ncost < Get(cost[nt_mod6], nx, ny)) {
                Set(cost[nt_mod6], nx, ny, ncost);
                que.push(State(nt_mod6, nx, ny, ncost));
            }
        }
        // その場から移動しない
        if (s.cost + 1 < Get(cost[(s.t_mod6 + 1) % 6], s.x, s.y)) {
            Set(cost[(s.t_mod6 + 1) % 6], s.x, s.y, s.cost + 1);
            que.push(State((s.t_mod6 + 1) % 6, s.x, s.y, s.cost + 1));
        }
    }
}

int main() {
    cin >> sx >> sy >> gx >> gy;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        Set(tile, x, y, -1);
    }
    cin >> lx >> ly;

    Dijkstra();

    int ans = kINF;
    for (int t_mod6 = 0; t_mod6 < 6; t_mod6++) {
        ans = min(ans, Get(cost[t_mod6], gx, gy));
    }

    if (ans < kINF) cout << ans << endl;
    else cout << -1 << endl;

    return 0;
}

感想

座標が凶悪ですが、やることは割と簡単なので(後まだPokemon Goをインストールできていないので)説明はこの程度で。