競技プログラミング用 知識集積所
ABC436D - Teleport Maze
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
ベースは典型的な迷路問題。
そこにワープの処理を足せばよい。
しかし、ワープ経路を「移動元、移動先」のペア全部で真面目に用意すると、最大盤面にほとんど全部aで埋められた場合に経路数が爆発して失敗するため、工夫がいる。
そこにワープの処理を足せばよい。
しかし、ワープ経路を「移動元、移動先」のペア全部で真面目に用意すると、最大盤面にほとんど全部aで埋められた場合に経路数が爆発して失敗するため、工夫がいる。
とはいえワープマスの処理も典型で、追加で26マス用意して、マスXからマスYへの文字aでのワープは、「マスX→マスa→マスY」という移動を行えばよい。
ただし、この移動は1ターンで行えるため、マスX→マスaは0ターンでの移動とする必要がある。
これは01最良優先探索※で実現できるし、なんなら普通の幅優先探索※を少し変えるだけでも書ける。
ただし、この移動は1ターンで行えるため、マスX→マスaは0ターンでの移動とする必要がある。
これは01最良優先探索※で実現できるし、なんなら普通の幅優先探索※を少し変えるだけでも書ける。
