はまやんはまやんはまやん

hamayanhamayan's blog

Bishop 2 [AtCoder Beginner Contest 246 E]

https://atcoder.jp/contests/abc246/tasks/abc246_e

前提知識

解説

https://atcoder.jp/contests/abc246/submissions/30681205

問題文とはxとyの解釈を逆にして説明している。
好みの問題ではあるのだが、つまり、チェス盤の上からy行目、左からx列目としてx,yを扱う。

今回の問題は最短経路問題であるため、最短経路問題と解くために使用されるダイクストラやBFSを
ベースに解法を作成していく。
これをベースに解法を考えていくと答えが導けたみたいな流れとなる。

拡張ダイクストラ

通常のダイクストラでは、頂点、つまり、場所だけを状態として考えて最短経路問題を行うが、
拡張ダイクストラでは、場所以外の何らかの情報(ないし状態)も合わせて状態を考えて最短経路問題を解くことを指す。
なので、状態の持ち方が変わるだけなので「拡張」という言葉をつける必要もないのだが、なんとなくついている。
ググるときに便利なワードではあるが、誤用というか不適切では?と言われることも多いので注意)

さて、状態としてどのマスにいるかということ以外にコストに関わってきそうなことを考えてみよう。
ビショップはポーンが無ければコストを増やすことなくずっと進んでいくので、ダイクストラのような1手ずつ
進んでいくことを前提に考えると、直前に(最後に)どの方向に移動したかという情報があれば、
コストがかかるかどうかを判別できそうである。
なので、ダイクストラを行う場合に以下のような配列(グラフ的には頂点か)を考えて更新していく。

opt[y][x][dir] := マス(x,y)にいて、直前に進んだ方向がdirである場合の、最小手数

後は、ダイクストラをしていくだけなので、それほど難しくない。
自分のコードは以下。
https://atcoder.jp/contests/abc246/submissions/30679961

int N;
int Ax, Ay, Bx, By;
string S[1510];

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int dx[4] = { 1, 1, -1, -1 };
int dy[4] = { 1, -1, 1, -1 };
int opt[1510][1510][5];
bool vis[1510][1510][5];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    //cin >> Ax >> Ay >> Bx >> By;
    cin >> Ay >> Ax >> By >> Bx;
    Ax--; Ay--; Bx--; By--;
    rep(y, 0, N) cin >> S[y];

    min_priority_queue<pair<int, tuple<int, int, int>>> que;
    rep(x, 0, N) rep(y, 0, N) rep(dir, 0, 5) opt[y][x][dir] = inf;
    rep(x, 0, N) rep(y, 0, N) rep(dir, 0, 5) vis[y][x][dir] = false;

    opt[Ay][Ax][4] = 0;
    que.push({ 0, { Ax, Ay, 4 } });

    while (!que.empty()) {
        int x, y, dir;
        tie(x, y, dir) = que.top().second;
        que.pop();

        if (vis[y][x][dir]) continue;
        vis[y][x][dir] = true;

        if (x == Bx && y == By) {
            cout << opt[y][x][dir] << endl;
            return;
        }

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx && xx < N && 0 <= yy && yy < N) {
                if (S[yy][xx] == '#') continue;
                if (chmin(opt[yy][xx][d], opt[y][x][dir] + (dir != d))) {
                    que.push({ opt[yy][xx][d], { xx, yy, d } });
                }
            }
        }
    }

    cout << -1 << endl;
}