競技プログラミング用 知識集積所
ABC431E - Reflection on Grid
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
全てのマス、全ての方向について、「そこをそのように通過するために必要な鏡の変更数」を最短経路問題として調べ切ればよい。
鏡を変更せずに行ける方向はコスト0、鏡を変更すれば行ける方向はコスト1なので、01最良優先探索※を使えばよい。
鏡を変更せずに行ける方向はコスト0、鏡を変更すれば行ける方向はコスト1なので、01最良優先探索※を使えばよい。
グラフの頂点は、マスの数H*W個それぞれに4方向と、最後のゴールで1つ、全部で4*H*W+1個分作るとよい。
問題は、同じマスを2回通る経路がある場合の扱い。
1度目と2度目で異なる角度の鏡にはできないことへのケアが必要そうに思える。
しかし実は、同じマスを2回通る場合は、1度目に入ってから2度目に出るまでの間でコストが1以上あるパターンは考えなくてよい。
なぜなら、その場合は直接目的の方向に曲げてしまえばコスト1でそのマスを1度しか通らない経路を作れるからである。
また、間がコストが0なのであれば、1度目と2度目で異なる角度の鏡になる状況は考えなくてよい。
よって、いろいろややこしいことが発生しそうな状況は全部無視できるのである。
1度目と2度目で異なる角度の鏡にはできないことへのケアが必要そうに思える。
しかし実は、同じマスを2回通る場合は、1度目に入ってから2度目に出るまでの間でコストが1以上あるパターンは考えなくてよい。
なぜなら、その場合は直接目的の方向に曲げてしまえばコスト1でそのマスを1度しか通らない経路を作れるからである。
また、間がコストが0なのであれば、1度目と2度目で異なる角度の鏡になる状況は考えなくてよい。
よって、いろいろややこしいことが発生しそうな状況は全部無視できるのである。
