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
- http://purple-jwl.hatenablog.com/entry/20130123/1358931139
- ここに書かれているように、bfsする時にprev配列にも値を入れておくのもいい
- これは蟻本に載っているそう