AtCoder: ABC176-D Wizard in Maze (400)

問題はこちら

atcoder.jp

縦 $H$ マス、横 $W$ マスからなる迷路がある。マス(i, j) は # のとき壁であり、. のとき道である。ます目 (C_h, C_w) から(D_h, D_w) に移動することを考える。

以下の二つの移動方法がある。

移動A: 現在いるマスと上下左右に隣接する道のマスへ移動する。
移動B: 現在いるマスを中心とする 5*5 の範囲内にあるマスへワープできる。

移動Bを最低で何回使う必要があるか答えよ。 (D_h, D_w) にたどり着けない場合は -1 を出力せよ。

考え方

まず、「なるべく移動Bを使わないで移動できるならそうした方が良い」というのがわかる。よって、まずは移動Aによって幅優先探索を行う。
そして、移動Aで訪れることのできるマスがなくなったとき、移動Bを使って移動することを考える。移動Bに関しては、今まで移動Aで訪れてきたマスを全て調査すれば良い。
移動Bで訪れることのできるマスを探索し終えたとき、訪れることのできるマスに対してを移動Aを行う（つまり1に戻る）

以上を繰り返すことで移動Bを使う回数を求めることができる。

1, 2を行うので全てのマス目に対して二回探索をする可能性が生じるが、それでも計算量は高々 $O(HW )$ なので間に合う。

解答

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll ll_inf = ll(1e9) * ll(1e9);
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main() {
    ll h, w;
    cin >> h >> w;
    ll startX, startY, endX, endY;
    cin >> startX >> startY >> endX >> endY;
    startX--, startY--, endX--, endY--;

    vector<vector<char>> s(h, vector<char>(w));
    rep(i, h) rep(j, w) cin >> s[i][j];

    vector<vector<ll>> cnts(h, vector<ll>(w, ll_inf));  // 魔法使った回数
    queue<P> q, visited;
    // q: 移動Aでの幅優先探索用
    // visited: 移動Bでの幅優先探索用
    q.push(P(startX, startY));
    cnts[startX][startY] = 0;

    while (!q.empty() || !visited.empty()) {
        ll nowX, nowY;
        if (!q.empty()) {
            nowX = q.front().first, nowY = q.front().second;
            visited.push(P(nowX, nowY));
            q.pop();
            rep(i, 4) {
                ll nextX = nowX + dx[i], nextY = nowY + dy[i];
                if (0 <= nextX && nextX <= h - 1 && 0 <= nextY && nextY <= w - 1) {
                    if (s[nextX][nextY] == '#') continue;
                    if (cnts[nowX][nowY] < cnts[nextX][nextY]) {
                        cnts[nextX][nextY] = cnts[nowX][nowY];
                        q.push(P(nextX, nextY));
                    }
                }
            }

        } else {  // 今まで通った道から魔法で行ける道を全て調べる
            nowX = visited.front().first, nowY = visited.front().second;
            visited.pop();
            for (ll ix = -2; ix <= 2; ++ix) {
                for (ll jy = -2; jy <= 2; ++jy) {
                    ll nextX = nowX + ix, nextY = nowY + jy;
                    if (0 <= nextX && nextX <= h - 1 && 0 <= nextY && nextY <= w - 1) {
                        if (s[nextX][nextY] == '#') continue;
                        if (cnts[nowX][nowY] + 1 < cnts[nextX][nextY]) {
                            cnts[nextX][nextY] = cnts[nowX][nowY] + 1;
                            q.push(P(nextX, nextY)); // 移動Bのあとは移動Aをしたいのでそちらの候補に入れる
                        }
                    }
                }
            }
        }
    }
    if (cnts[endX][endY] == ll_inf) {
        cout << -1 << '\n';
    } else {
        cout << cnts[endX][endY] << '\n';
    }
    return 0;
}

Submission #16164015 - AtCoder Beginner Contest 176

ひらめの日常

日常のメモをつらつらと

AtCoder: ABC176-D Wizard in Maze (400)

問題はこちら

考え方

解答