perogram

C - ダブレット ~経路復元~

f:id:peroon:20190725190223j:plain

Quiz

https://arc011.contest.atcoder.jp/tasks/arc011_3

AC Code

https://arc011.contest.atcoder.jp/submissions/6535492

解法

  • wordをグラフのNodeとする
  • 編集距離が1のNode同士をつなげる
    • (編集距離と言っていいのは微妙。追加・削除がないので)
  • bfsでfirst wordからlast wordまで到達できるか調べる

経路復元 私Ver

  • 行けることが確定しているならゴールからスタートにたどればいい
  • たどるごとに距離が1小さいNodeに移動すればいい

経路復元 蟻本Ver