【AtCoder】ABC 387 D - Snaky Walk | 緑コーダーが解くAtCoder

配点: 400 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 817

問題概要
制約
考察
実装例
コメント

問題概要

$H \times W$ のグリッドがある。以下では、上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表記する。

各マスはスタートマス・ゴールマス・空きマス・障害物マスのいずれかであり、その情報は $H$ 個の長さ $W$ の文字列 $S_1,S_2,\cdots,S_H$ によって表され、

$S_{i, j} =$ S : $(i, j)$ はスタートマス
$S_{i, j} =$ G : $(i, j)$ はゴールマス
$S_{i, j} =$ : $(i, j)$ は空きマス
$S_{i, j} =$ # : $(i, j)$ は障害物マス

である。なお、スタートマスとゴールマスはちょうど1つずつ存在することが保証される。

あなたは今スタートマスにいて、これから「今いるマスと辺で隣接するマスに移動する」ことを繰り返してゴールマスへ行くことを目指す。ただし、障害物マスやグリッドの外に移動することはできず、また縦移動と横移動を1回ずつ交互に行わなければならない(最初の移動の向きは任意)。

このとき、ゴールマスへ行くことが可能であるか判定し、可能ならば移動回数の最小値を求めよ。

制約

$1\leq H,W \leq 1000$
$H,W$ は整数。

考察

本記事では、幅優先探索(BFS)の基本は理解していることを前提とする。 BFS の基本については、けんちょんさんの記事等を参照のこと。

1つのスタートからの最小移動回数を求める、単一始点最短経路問題。これは BFS 一択でいいだろう。

ただ一つ厄介なのは、隣接マスへの移動を縦と横交互に行わなければならない点だ。普通の BFS で用いる、スタートから各マスまでの最短距離を格納する二次元配列では、この条件に対応できない。

...ということで、この配列にもう1次元追加して、移動方向の情報も格納することを考える。具体的には、以下のような3次元配列distを構築する。

$\mathrm{dist}_{i, j, d} :=$ 次に移動する方向が $d \: (d = 0 \Rightarrow 縦移動, \: d = 1 \Rightarrow 横移動)$ であるときの、スタートマスから $(i, j)$ までの最短移動回数

また、queueにも以下のような、移動方向を含めた構造体State型で情報を格納していく。

struct State
{
    int i, j, dir;
};

さらに、移動方向を表すベクトルもちょっと工夫しておく。これにより、次に探索するマスを列挙するときの処理が少し楽になる。

// 2次元配列の1つ目の添字で縦 or 横を決定、2つ目の添字で (上 or 下) / (左 or 右) を決定
int di[2][2] = {{-1, 1}, {0, 0}};
int dj[2][2] = {{0, 0}, {-1, 1}};

以下、今回のアルゴリズムの流れを簡単に示す。

スタートマスのdistを2方向とも0で初期化。queueに「スタートマスから縦移動」と「スタートマスから横移動」の状態をそれぞれpushする。
queueからになるまで以下を繰り返す。
1. queueの先頭要素(nowとする)をpopし、di, djの2つ目の添字 $k = 0, 1$ について、それぞれ以下の処理を行う。
2. 次に移動するマスは、例えば $i$ 成分なら $\mathrm{now}_i + \mathrm{di}_{\mathrm{now}_{\mathrm{dir}}, k}$ のように計算できる。
3. また、次の移動方向は $d : 0 \rightarrow 1, \: 1 \rightarrow 0$ なので、例えば $(\mathrm{now}_{\mathrm{dir}} + 1) \mod 2$ のように計算できる。
4. 次に移動するマスがグリッド外及び壁ではない、かつ未訪問のマスであるならば、distの対応する要素を $\mathrm{dist}_{\mathrm{now}_i, \mathrm{now}_j, \mathrm{now}_{\mathrm{dir}}} + 1$ で更新する。queueにも対応する情報をpushする。
ゴールマスのdistについて、2つの方向のうち小さいものを答えの候補とする。もしそれがINFならば、スタートマスからゴールマスへ到達できなかったことを示すので-1を出力する。そうでなければ、そのまま出力する。

計算量はグリッド上の BFS なので $O(HW)$ であるが、今回の制約下では十分高速。

実装例

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

constexpr int INF = 1e+9;

using Pair_int = pair<int, int>;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int di[2][2] = {{-1, 1}, {0, 0}};
int dj[2][2] = {{0, 0}, {-1, 1}};

struct State
{
    int i, j, dir;
};

int main()
{
    int H, W;
    cin >> H >> W;
    vector<vector<char>> grid(H, vector<char>(W));
    Pair_int start, goal;
    rep(i, 0, H)
    {
        rep(j, 0, W)
        {
            cin >> grid[i][j];

            if (grid[i][j] == 'S')
                start = {i, j};

            if (grid[i][j] == 'G')
                goal = {i, j};
        }
    }
    vector<vector<vector<int>>> dist(H, vector<vector<int>>(W, vector<int>(2, INF)));
    dist[start.first][start.second][0] = 0;
    dist[start.first][start.second][1] = 0;

    queue<State> que;
    que.push({start.first, start.second, 0});
    que.push({start.first, start.second, 1});

    while (!que.empty())
    {
        State now = que.front();
        que.pop();

        rep(k, 0, 2)
        {
            int ni = now.i + di[now.dir][k];
            int nj = now.j + dj[now.dir][k];
            int nd = (now.dir + 1) % 2;

            if (ni < 0 || ni >= H || nj < 0 || nj >= W)
                continue;

            if (grid[ni][nj] == '#')
                continue;

            if (dist[ni][nj][nd] != INF)
                continue;

            dist[ni][nj][nd] = dist[now.i][now.j][now.dir] + 1;
            que.push({ni, nj, nd});
        }
    }

    int ans = min(dist[goal.first][goal.second][0], dist[goal.first][goal.second][1]);
    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return 0;
}