Obstruction（code festival 2014 上海 [I]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

解法

ゴールへ到達可能だと判明しているマス全体の集合 $S$ を、以下のルールで生成します。

• ゴールマスは $S$ に含まれる
• 隣接している黒マスのいずれかが $S$ に含まれるならば、そのマスは $S$ に含まれる
• 隣接している白マスのうち 2 つ以上が $S$ に含まれるならば、そのマスは $S$ に含まれる

ゴールマスから初めて、新しく $S$ の要素だと判明したマスの周辺を探索するようにすれば、$S$ は $O(N^2)$ 時間で生成できます（$S$ の要素だと判明したマスをキューなどに入れていく）。

$S$ に含まれないマスからは、X 氏が適切に妨害すれば、移動先を $S$ に含まれないマスに限定できます。したがって、そのようなマスからの到達は保証できません。したがって、$(0,0)$ が $S$ に含まれるかどうかにしたがって YES / NO を出力すればよいです。