[AtCoder] ABC 132 E – Hopscotch Addict

2019年7月1日

問題

方針

ステップ数が \( 3 \) の最短距離の探索

例えば、ステップ数が \( 3 \) の最短経路の探索では、スタート地点から \( 3 \) ステップ目で到達可能な頂点を距離 \( 1 \) で到達可能な頂点とします。また、この到達した頂点から探索を行います。この探索において、\( i \) ステップ目で訪れた頂点 \( j \) のフラグを \( f_{i, j} \ (1 \leq i \leq 3 \wedge 1 \leq j \leq N)  \) とします。\( f_{3, T} = 1 \) ならば、到達可能です。

幅優先探索を行うことを考えます。\( S \) から \( i \) までの最短距離を \( d_i \) とます。キュー \( q \) に \( S \) を入れます。そして、\( f_{3, S} = 1 \) とします。

頂点 \( S \) から \( 1 \) ステップで行くことができる頂点 \( i \) のフラグ \( f_{1, i} \) を調べ、フラグが立っていなければ探索を止めて、そうではなければ探索を続け、その頂点 \( i \) に訪れます。つぎに、\( i \) から \( 1 \) ステップで行くことができる頂点 \( j \) のフラグ \( f_{2, j}\) を調べ、フラグが立っていなければ探索を止め、そうではなければ探索を続け、その頂点 \( k \) に訪れます。\( f_{3, k} = 0 \) であれば、\( d_k = d_i + 1 \) とします。そして ( q \)  に \( k \) を挿入します。

コード