AOJ 2425 A Holiday of Miss Brute Force

全探索お姉さんとアルゴリズムお姉さんはどっちが先だったんだろう？

問題

A Holiday of Miss Brute Force | Aizu Online Judge

解法

時間に関しては 6 で割ったあまりのみを考えれば良いです。

そう考えると, d[t][x][y] = (時間 t に x, y にたどり着けるような時, 指示を無視する最小値) というようなものを考えれば良さそうです。これは最短経路問題になります。ダイクストラとかで処理しましょう。

少し面倒なのがある座標から方向 i に進むと次の座標がどうなるか, ですが, 観察すると x 座標の偶奇に依存して y 座標も変化するか変わらないかが決まっていることがわかります。

struct edge {
    int v;
    ll w;
    edge() {}
    edge(int v, ll w) : v(v), w(w) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

const int B = 111;
bool ng[2*B][2*B];
int Lx, Ly;
const int INF = 1e9;

pii move(int x, int y, int dir) {
    int nx = x, ny = y;
    switch (dir) {
    case 0:
        ny += 1;
        break;
    case 3:
        ny -= 1;
        break;
    case 1:
        nx += 1;
        if (x%2) ny += 1;
        break;
    case 2:
        nx += 1;
        if (x%2 == 0) ny -= 1;
        break;
    case 4:
        nx -= 1;
        if (x%2 == 0) ny -= 1;
        break;
    case 5:
        nx -= 1;
        if (x%2) ny += 1;
        break;
    }
    if (abs(nx) > Lx || abs(ny) > Ly || ng[nx+B][ny+B]) {
        nx = -B;
        ny = -B;
    }
    return pii(nx, ny);
}

int getVertex(int t, int x, int y) {
    x += B; y += B;
    int ret = t;
    ret = ret*2*B + x;
    ret = ret*2*B+y;
    return ret;
}

int main() {
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        ng[x+B][y+B] = true;
    }
    cin >> Lx >> Ly;
    vector<vector<edge> > G(6*2*B*2*B);
    for (int t = 0; t < 6; t++) {
        for (int x = -Lx; x <= Lx; x++) for (int y = -Ly; y <= Ly; y++) {
            int v = getVertex(t, x, y);
            int should = abs(t*x*y)%6;
            for (int i = 0; i <= 6; i++) {
                auto next = move(x, y, i);
                if (next.first == -B) continue;
                int u = getVertex((t+1)%6, next.first, next.second);
                int cost = 1;
                if (i == should) cost = 0;
                G[v].emplace_back(u, cost);
            }
        }
    }
    auto d = dijkstra(6*2*B*2*B, G, getVertex(0, sx, sy));
    ll ans = INF;
    for (int i = 0; i < 6; i++) {
        ans = min(ans, d[getVertex(i, gx, gy)]);
    }
    if (ans >= INF) ans = -1;
    cout << ans << endl;
    return 0;
}