Mister雑記

競プロやります。

AOJ 2425 「全探索お姉さんの休日」

onlinejudge.u-aizu.ac.jp

問題

あなたと全探索お姉さんは正六角形が敷き詰められた空間のマス (sx, sy)にいる。ここから毎分隣接するマスへの移動を繰り返すことで、マス (gx, gy)に行きたい。

ただし障害物が置かれているマス、 x座標の絶対値が lxより大きい、または y座標の絶対値が lyより大きいマスには入れない。

さらに厄介なことに、お姉さんは毎分座標と時刻に基づいて適当な方向に移動するように指示する。目的地に着くまでにお姉さんの指示を無視する回数を最小化せよ。

制約

  • 障害物は 1,000個以下
  •  0 \lt lx, ly \leq 1,000

考察

座標の指定方法が気持ち悪いため、 x座標の偶奇で隣接するマスの相対位置が変わっていることに注意。

まずBFSが思いつくが、お姉さんの指示が時間に依存しているため時刻も状態として持つ必要がある。お姉さんの指示は時刻を6で割った値にしか依存しないため、これと座標を組にすると状態数を 2lx \cdot 2ly \cdot 6 = 24 lx \cdot lyに抑えられる。

後はBFSだが、お姉さんの指示に従った場合距離は増えないため普通のBFSは無理。Dijkstraでもいいのだが、ここでは01-BFSを実装した。

01-BFSは「距離が増加しない場合はdequeの先頭に突っ込む」以外はBFSと全く同じ、と思っていた時期が僕にもありましたDijkstraと同様に再探索を防ぐ機構が必要なので注意。

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <deque>
#include <tuple>

using namespace std;

using lint = long long;
using ldouble = long double;

const int INF = 1 << 30;

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

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

    int N;
    cin >> N;
    vector<int> ox(N), oy(N);
    for (int i = 0; i < N; ++i) {
        cin >> ox[i] >> oy[i];
    }

    int lx, ly;
    cin >> lx >> ly;

    // 全体をlx, lyだけずらして非負整数座標にする
    sx += lx, sy += ly, gx += lx, gy += ly;
    int H = lx * 2, W = ly * 2;
    vector<vector<bool>> obj(H + 1, vector<bool>(W + 1, false));
    for (int i = 0; i < N; ++i) {
        obj[ox[i] + lx][oy[i] + ly] = true;
    }

    // お姉さんの指示に逆らった回数 with 時刻
    vector<vector<vector<int>>> dist(H + 1, vector<vector<int>>(W + 1, vector<int>(6, INF)));
    dist[sx][sy][0] = 0;

    deque<tuple<int, int, int, int>> que;
    que.emplace_front(sx, sy, 0, 0);

    // 01-BFS
    while (!que.empty()) {
        int x, y, t, d;
        tie(x, y, t, d) = que.front();
        que.pop_front();

        // Dijkstraと同じくこのfilterが必要なので注意
        if (d > dist[x][y][t]) continue;

        int dir = abs((x - lx) * (y - ly) * t) % 6;  // お姉さんの指示
        int nt = (t + 1) % 6;

        for (int i = 0; i < 7; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[abs(x - lx) % 2][i];

            if (nx < 0 || H < nx || ny < 0 || W < ny ||
                obj[nx][ny] || dist[nx][ny][nt] <= dist[x][y][t] + (i != dir)) continue;

            if (i == dir) {
                // 指示に従うなら距離は増えない
                dist[nx][ny][nt] = dist[x][y][t];
                que.emplace_front(nx, ny, nt, dist[nx][ny][nt]);
            } else {
                dist[nx][ny][nt] = dist[x][y][t] + 1;
                que.emplace_back(nx, ny, nt, dist[nx][ny][nt]);
            }
        }
    }

    int ans = INF;
    for (int t = 0; t < 6; ++t) {
        ans = min(ans, dist[gx][gy][t]);
    }
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

反省

  • 01-BFSに関する知見が得られた。
    • 解説見たらDijstra法でお気持ちになった。