名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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)