ABC168 D - .. (Double Dots) が解けて、叫ぶ

問題

思考のプロセス

・絵をかいて理解に努める
 入力例1

 入力例2

 とりあえず、絵を眺めて考えた。
 ステップとして以下のように分けて考えた方が良いと思いました。

・Yes or No を判定する事だけ考える
 何気なく書いた上図の赤丸の図に注目しました。
 部屋1 から START し、全ての部屋に BFS で探索できた場合、
 メモした工程数は 各部屋から 部屋1 への最短距離と言えませんか？
 入力例2であれば、部屋 3 <=> 部屋 4 、部屋 4 <=> 部屋 2 が繋がっているので
 BFS が上手くいきません(勿論 部屋 5 <=> 部屋 6 も しかりです。)。
 そこはコードに工夫が必要です。

・Yes の場合、道しるべを如何に用意するか考える
 求められるアクションは以下だと思いました。

  部屋 1 => 部屋 5 に移動した場合、部屋 1　から来たことになります。
  よって部屋 5 には道しるべ 1 を配置

  部屋 1 => 部屋 6 に移動した場合、部屋 1　から来たことになります。
  よって部屋 6 には道しるべ 1 を配置

  部屋 5 => 部屋 3 に移動した場合、部屋 5　から来たことになります。
  よって部屋 3 には道しるべ 5 を配置

  部屋 5 => 部屋 4 に移動した場合、部屋 5　から来たことになります。
  よって部屋 4 には道しるべ 5 を配置
           ・
           ・
           ・
           ・
 これは BFS で移動する度にメモしていけばクリアできる気がしました。

コードに落とす

 以下で AC でした。
 https://atcoder.jp/contests/abc168/submissions/35937244
 今回は BFS の本質(特徴)を捉えて応用できるかを問われている気がしました。

 楽しかった! 出会いに感謝 m(_ _)m