No.3 ビットすごろく

幅優先探索 yukicoder

Quiz

https://yukicoder.me/problems/no/3

Submit

https://yukicoder.me/submissions/330413

解法

  • ある地点からの移動先は(2箇所以下に)固定されている
  • よって、ある地点に戻って来たら、それは最短距離ではない
  • 同じ地点を訪れないようにしながら最短距離を探索すればよく、それはマス目上の迷路の最短距離の解き方と同様
    • 幅優先探索

幅優先探索と迷路

bitを数える

  • bitsetを使ってみた
        // ビットの数
        bitset<20> bs(index);
        ll bit_count = bs.count();

今回の問題の注意点

  • 始点を距離1と数えること
    • 普通は距離0が多い