[AtCoder] ABC 176 D – Wizard in Maze

問題

方針

領域の作成

徒歩で行くことができるマスをグループ化し、IDを振ります。マス \( (i, j) \) の ID が \( 0\) であることを \( G(i, j) = 0 \) と表し、そのマスから徒歩でいけるマスの ID は \( 0\) となります。 これらは幅優先探索で求めることができます。

隣接リストの作成

道であるマス \( (i, j) \) から \( |i + x| \leq 2 \wedge |i + y| \leq 2 \) を満たす \( x, y\) について、マス \( (i + x, j + y) \) が道であるときワープ魔法で移動することができます。このとき、\( G(i, j) \neq G(i + x, j + y) \) であれば辺として追加します。

隣接リストの探索

隣接リストが作成できたら、\( G(C_w, C_h) \) から探索し、\( G(D_w, D_h) \) までの最短距離を調べます。

コード