ABC 401-500/ABC454E - LRUD Moving - 競技プログラミング用 知識集積所

---

問題

ABC454E

必要知識

B以下レベルの内容は省略

• 考察問題
• 二部グラフ※（の考え方）

考え方

グリッド上の縦横移動問題なので、この問題は二部グラフ※の性質を持つ。
つまり、マス(i,j)は、i+jが偶数のときにはグループX、奇数のときにはグループYと考えると、全ての移動はXY間の移動となる。
スタートとゴールはどちらもXなので、XがYより1つ多い状態になっていなければ不可能である。
具体的には、Nが奇数のとき（XとYが合わせて偶数個）や、Nが偶数だがA+Bが偶数のとき（AがBより1個少ない）には不可能である。

では、Nが偶数かつA+Bが奇数のときに必ず可能か？
これは、可能で、方法はいろいろある。

一例として、以下のような方法でよい。

• 基本的には「最上段を端から端まで右方向へ、次の行は端から端まで左方向へ、次は右へ」と大蛇行をする
• 右へ行くときに、この行か次の行に通行禁止マスがあったら、そこだけ2行を上下に蛇行して回収する

こうすると、通行禁止マスが（1-indexで）

• 奇数行目偶数列目にある場合は、そこの下を通るときに2連続右移動すればよい
• 偶数行目奇数列目にある場合は、そこの上を通るときに2連続右移動すればよい

という部分をどう実装するかという問題になる。
これは、蛇行しながら「通行禁止マスと同じ列になったら右移動する」を随時チェックするだけでよい。

解答例

解答例

注意点

別解