2022-04-03

AtCoder ABC 246 E - Bishop 2 (水色, 500 点)

迷路の最短路問題なので BFS でやりたくなるが、まともにやると $O(N^{3})$ で TLE してしまう！！

頂点の持ち方を工夫して 0-1 BFS で解く！
別解として枝刈り BFS も。

drken1215.hatenablog.com

問題へのリンク

問題概要

$N \times N$ のグリッドが与えられます。各マスは通路 (文字 . で表される) と壁 (文字 # で表される) のいずれかです。

今あなたは座標 (Ax, Ay) にいます。ここから「ビショップの移動」を繰り返して座標 (Bx, By) に到達したいとします。そのための最小手数を答えてください。到達不可能な場合は -1 と出力してください。

なおビショップの移動とは「斜め四方向に、壁にぶつからない限りはどこまでも移動できる」というものです。壁を通り抜けたり、盤面外に出たりすることはできません。

制約

$2 \le N \le 1500$

BFS では間に合わない

「迷路の最短路」は BFS の典型問題です。ただし通常の「迷路の最短路」問題では、1 回で移動できるマスが「上下左右に隣接する 4 マス」しかないのに対して、今回の問題では 1 回で $O(N)$ 個のマスに移動できうそうです。

BFS の計算量はグラフの辺数 $E$ に対して $O(E)$ です。1 回で移動できる箇所が $O(N)$ となると、グラフの辺数は $O(N^{3})$ になります。よって単なる BFS だと、計算量は $O(N^{3})$ となって間に合いません。

ノードに「移動方向」を持たせて 1 マスずつ移動する

そこで、「1 回の移動で斜めにどこまでも進める」というのを次のように読み替えることにします。

各頂点が (縦方向座標, 横方向座標, 前回の移動方向) を表すグラフを考える
各頂点に対して斜め四方向に進んだ 4 マスにのみ辺を張る
- 移動方向が前回のものと一致するときは「辺のコスト：0」
- 移動方向が前回のものと異なるときは「辺のコスト：1」

こうしてできるグラフ上で、(Ax, Ay, 任意) を始点、(Bx, By, 任意) を終点とした最短経路問題を解けばよいことになります！！

こうしてグラフの辺数が $O(N^{2})$ で抑えられることになりました。ただし元々のグラフでは辺のコストがすべて 1 だとみなせたのに対して、今回は辺のコストは 0 と 1 がありうることになります。

普通の BFS ではダメなので、Dijkstra 法や 0-1 BFS を使います。

0-1 BFS

0-1 BFS は、辺のコストが 0, 1 のみに限ることを利用して、Dijkstra 法における priority_queue の部分を deque にすることで計算量を落とす手法です。Dijkstra 法の計算量 $O(V + E \log V)$ が、0-1 BFS では $O(V + E)$ に落ちます。

辺の重みが 0 と 1 のみに限られるとき、Dijkstra 法を回したときの priority_queue の中身は常に「最大値と最小値との差が 1 以下」という状態が保たれます。　

よって、priority_queue の中身は高々 2 種類の値しか同時に共存しないことになります。priority_queue のような高級なデータ構造を使う必要はありません。代わりに

両端キュー deque を使う

という方法が考えられます。そして辺 $e = (u, v)$ について緩和するとき、

辺のコストが 0 の場合：deque の先頭に push
辺のコストが 1 の場合：deque の末尾に push

というようにすればよいことになります。deque の両端に push する操作は $O(1)$ でできるので、priority_queue を使うのに比べて計算量が落ちます。

今回の場合、計算量は $O(N^{2})$ になります。

コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 29;
const vector<int> dx = {1, 1, -1, -1};
const vector<int> dy = {1, -1, 1, -1};

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { 
        a = b; 
        return true; 
    } 
    return false;
}

int main() {
    // 入力
    int N, Ax, Ay, Bx, By;
    cin >> N >> Ax >> Ay >> Bx >> By;
    --Ax, --Ay, --Bx, --By;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];

    // 頂点数は (N x N x 4)
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(4, INF)));
    deque<tuple<int,int,int>> que;

    // 初期条件
    for (int dir = 0; dir < 4; ++dir) {
        dp[Ax][Ay][dir] = 1;  // 最初の 1 手をノーコストにするため
        que.push_back({Ax, Ay, dir});
    }

    // 0-1 BFS
    while (!que.empty()) {
        auto [x, y, dir] = que.front();
        que.pop_front();
        
        for (int ndir = 0; ndir < 4; ++ndir) {
            int nx = x + dx[ndir], ny = y + dy[ndir];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (S[nx][ny] == '#') continue;

            int cost = (ndir != dir);
            if (chmin(dp[nx][ny][ndir], dp[x][y][dir] + cost)) {
                if (cost == 0) que.push_front({nx, ny, ndir});
                else que.push_back({nx, ny, ndir});
            }
        }
    }
    int res = INF;
    for (int dir = 0; dir < 4; ++dir) chmin(res, dp[Bx][By][dir]);
    cout << (res < INF ? res : -1) << endl;
}

別解：枝刈り BFS

さきほど、通常の BFS では TLE してしまうと書いたが、少し工夫することで通すことができる。

通常の BFS では、今いるマスから、斜め四方に壁にぶつからない限りどこまでも行く遷移を試す。

下のコードのような感じ。このコードは、移動方向 dir を決めた上で、その方向に壁にぶつかるまで遷移する様子を表している。

while (true) {
      x += dx[dir], y += dy[dir];
      if (x < 0 || x >= N || y < 0 || y >= N) break;
      if (S[x][y] == '#') break;
                
      if (chmin(dp[x][y], cur_dist + 1)) {
             que.push({x, y});
      } 
}

枝刈り BFS は、次のように「もともとの距離値がより小さいようなマスに到達したら打ち切る」ようにするだけ！！！

while (true) {
      x += dx[dir], y += dy[dir];
      if (x < 0 || x >= N || y < 0 || y >= N) break;
      if (S[x][y] == '#') break;

      if (dp[x][y] < cur_dist + 1) break;
                
      if (chmin(dp[x][y], cur_dist + 1)) {
             que.push({x, y});
      } 
}

たったこれだけの工夫で劇的に早くなる。

コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1 << 29;
const vector<int> dx = {1, 1, -1, -1};
const vector<int> dy = {1, -1, 1, -1};

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { 
        a = b; 
        return true; 
    } 
    return false;
}

int main() {
    // 入力
    int N, Ax, Ay, Bx, By;
    cin >> N >> Ax >> Ay >> Bx >> By;
    --Ax, --Ay, --Bx, --By;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];

    // 頂点数は (N x N)
    vector<vector<int>> dp(N, vector<int>(N, INF));
    queue<pair<int,int>> que;

    // 初期条件
    dp[Ax][Ay] = 0;
    que.push({Ax, Ay});

    // 枝刈り BFS
    while (!que.empty()) {
        auto [cx, cy] = que.front();
        que.pop();
        int cur_dist = dp[cx][cy];
        for (int dir = 0; dir < 4; ++dir) {
            int x = cx, y = cy;
            while (true) {
                x += dx[dir], y += dy[dir];
                if (x < 0 || x >= N || y < 0 || y >= N) break;
                if (S[x][y] == '#') break;

                if (dp[x][y] < cur_dist + 1) break;
                
                if (chmin(dp[x][y], cur_dist + 1)) {
                    que.push({x, y});
                } 
            }
        }
    }
    cout << (dp[Bx][By] < INF ? dp[Bx][By] : -1) << endl;
}