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

hamayanhamayan's blog

Stronger Takahashi [AtCoder Beginner Contest 213 E]

競技プログラミング

https://atcoder.jp/contests/abc213/tasks/abc213_e

前提知識

解説

https://atcoder.jp/contests/abc213/submissions/24896937

確かに01BFSで解けるというか、まんまですね…
最終的な最短距離を求める方法がダイクストラでもいいし、計算量がより良い01-BFSでもいいしという感じです。
本解説では、辺の貼り方を重点的に説明するので、そのあたりを理解してもらえれば、あとはどっちかを使って計算する感じです。
あと、01-BFSの解説は以下がオススメです。
01-BFSのちょっと丁寧な解説 - ARMERIA
一応はっきりさせておくと、今回はコスト0の辺があるので普通のBFSだとWAします。

最短経路問題

今回の問題は最短経路問題であり、その場合によく使われるダイクストラとかその方面で考え始めることができれば答えに近づくことができる。
ダイクストラで問題を解く方向で考えていこう。
（最終的に辺のコストは0か1になるので、01-BFSでも解けるねってなります）
パンチという条件がかなり珍しい条件であるので、それをいかに条件に組み込めるかが重要になる。

隣接移動

隣接するマスへの移動は壁が無ければコスト無しで（パンチ無しで）移動することができる。
よって、隣接する4マスについては壁が無ければ辺のコスト0で辺を貼ることにする。
これはいいだろう。

パンチ

パンチを1回繰り出すことで移動できる場所について考えてみる。

.ooo.  
ooooo  
ooxoo  
ooooo  
.ooo.

現在xにいるとして周りがすべて壁に囲まれていたと仮定すると、oがついている所はすべて1回のパンチで移動可能となる。
よって、xからoへの遷移はコスト1の辺を貼ってしまっていい。
要は、この移動に関しては壁があるかどうかにかかわらずパンチして移動すると考えるのである。

こうすると、無駄にパンチを打ってしまいそうな気もするのだが、コスト0の隣接移動も辺は貼っているので、
パンチの必要が無ければそっちの辺が採用されて最適解が求まる。

これはダイクストラとかでよく自分が使うテクだが、無駄な辺があっても実装が楽になるなら残しておくようにしている。
実際は間に壁が無ければコスト1の辺は貼る必要はないのだが、あっても最適解は求まるので、
大変な判定を実装するよりかはそのまま貼ってしまってアルゴリズムに任せる方針をよく取る。
（非本質な延長線上のテクだが、辺の貼り方にあんまり自信がないときに関係なさそうだけど貼っとくかという感じで無駄な辺を貼ってみたりもする）
（こんなことしてるから競プロが上達しない）

あとは最短経路を求めるだけ

普通にダイクストラを書いて、遷移可能な隣接する4マスへコスト0の辺と、パンチで遷移可能なマスへコスト1の辺の遷移をすれば答えまで導ける。
パンチでの遷移については、[y-2,y+2]と[x-2,x+2]の2重ループでうまいこと書いた。
端っこだけ遷移できないので、マンハッタン距離が4の場合は遷移しないようにした。
無駄な(x,y)から(x,y)へのコスト1の遷移も含まれているが、前述の理由により残している。

int H, W;
string S[505];
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int vis[505][505];
int opt[505][505];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    rep(y, 0, H) rep(x, 0, W) opt[y][x] = inf;
    
    min_priority_queue<pair<int, int>> que;
    que.push({ 0, 0 });
    opt[0][0] = 0;

    while (!que.empty()) {
        auto p = que.top(); que.pop();

        int cst = p.first;
        int y = p.second / W;
        int x = p.second % W;      

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

        rep(d, 0, 4) {
            int xx = x + dx[d];
            int yy = y + dy[d];
            if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                if (S[yy][xx] == '.') {
                    if (chmin(opt[yy][xx], opt[y][x])) {
                        que.push({ opt[yy][xx], yy * W + xx });
                    }
                }
            }
        }

        rep(yy, y - 2, y + 3) rep(xx, x - 2, x + 3) {
            if (abs(x - xx) + abs(y - yy) == 4) continue;
            if (0 <= xx && xx < W && 0 <= yy && yy < H) {
                if (chmin(opt[yy][xx], opt[y][x] + 1)) {
                    que.push({ opt[yy][xx], yy * W + xx });
                }
            }
        }
    }

    cout << opt[H - 1][W - 1] << endl;
}