perogram

C - 壁抜け (abc020_c)

Quiz

https://atcoder.jp/contests/abc020/tasks/abc020_c

Submit

https://atcoder.jp/contests/abc020/submissions/4023131

補足

  • xを二分探索。探索1回ごとにワーシャルフロイドで最短経路を求める
  • 私の場合、今までワーシャルフロイドを使うときは双方向で同じコストだったが今回は違う
    • このアルゴリズムは「なぜか求まる」という理解しかしていないのでデバッグでハマると大変そう
  • どんなテストケースであれ、10x10の領域で考えた
    • しかし、デバッグを考えるとH, Wを使った方がよかったと思うので次回はそうする

補足2:ワーシャルフロイドをどうやった?

f:id:peroon:20190116124444j:plain

  • このやり方でうまくいってよかった
  • 幅優先とかでサラッと書けそうで書けない(迷路とは違う)🤔