競技プログラミング用 知識集積所

ABC413G - Big Banned Grid

最終更新:

sport_programming

- view
管理者のみ編集可


問題


必要知識

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

考え方

サイズがもう少し小さければ普通にC問題レベルの幅優先探索(未作成)問題。
しかし今回は、HWが10^10以上になるので、それができない。

そこで、双対性(未作成)を利用して、つまり
  • 左上マスから障害物のないマスだけを縦横に移動して右下マスまで行けるか?
  • 左辺か下辺から障害物のあるマスだけを縦横斜めに移動して上辺か右辺まで行けるか?
の答えが絶対に逆になることを利用する。

下側の問題は、通れるマスがkマスしかなく、毎回8方向全部見ても計算量的には余裕である。
問題は到達可能性を二重vector(未作成)で持てないこと。
仕方がないのでset(未作成)で障害物のある未到達マスを管理するように実装する。

解答例


注意点



別解

タグ:

幅優先探索
ウィキ募集バナー