白駿/鬼ごっこ

Question
質問リンク
Silver 1
Logic
デフォルト構造:bfs
1.NはKが3つに分かれた場合の数となる.

2n, n-1, n+1

私はグラフの角度からこの問題を見た.nからkまでの最短距離のグラフ.方法はdfsとbfsである.

であるが、nの子孫にはn−1およびn+1があり、dfsが選択されると無限ループに陥る.

したがって、bfsを選択し、dequeではなくlistとpop(0)を使用します.

時間を短縮するために、辞書へのアクセスとして実装される.

各場合のノード数が0未満、100000を超え、アクセスしたノードは計算されません.

Code

from sys import stdin
from sys import stdin

n = 0
def bfs(n,k):
    visited={i:0 for i in range(100001)}
    queue = [(n,0)]
    while queue:
        n = queue.pop(0)
        num=n[0]
        if num == k : break
        if num<0 or num>100000 : continue
        if visited[num]==1 : continue
        visited[num]=1
        for nn in [num*2, num-1, num+1] : queue.append((nn,n[1]+1))
    return n[1]

N,K = map(int,stdin.readline().rstrip().split())
print(bfs(N,K))