読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.3 ビットすごろく

回答

#44663 No.3 ビットすごろく - yukicoder

幅優先探索で見つける.見つからない場合は,到達不可能.-1を出力.
探索回数はちゃんとメモすること.(最初忘れてた)

幅優先探索,こういう書き方ばかりしているが,もっと効率良くかけるような気がする….
他の人のソースコード読まないとなあ(白目)

N = int(input())
numberlist = []
for i in range(1, N+1):
    num = str(bin(i)).count("1")
    numberlist.append(num)
visited = set([1])
search = [[1, 1]]

while len(search) > 0:
    cur, turn = search.pop(0)
    if cur == N:
        print(turn)
        exit(0)
    mv = numberlist[cur-1]
    if cur - mv > 1 and (cur - mv) not in visited:
        search.append([cur - mv, turn + 1])
        visited.update(set([cur - mv]))
    if cur + mv <= N and (cur + mv) not in visited:
        search.append([cur + mv, turn + 1])
        visited.update(set([cur - mv]))

print(-1)