読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CS Academy: A Single One

問題ページ

解法

単純に BFS するのは難しいが、遷移先候補がほぼ連続であることを用いると BFS ができる。

$K=5$ のとき移動できる箇所は次のようになっている。

f:id:pekempey:20160823144243p:plain

移動できる場所は(偶奇が異なる場所を無視すれば)連続している。そのため、未到達の点を 2 つの set で持てば無駄なく遷移先を見つけられる。

配列の端の処理が結構面倒。

解けて良かった。