白駿13549パイソン

質問する

かくれんぼをする

白駿13549

に答える

かくれんぼに似ている.
解法は同じで,結果値を探す過程の末尾部分だけを変えた.
かくれんぼをする

置換部分1

瞬間移動では時間は増えません.(0秒後)
そこでdequeのappendleft()を用いてコードを変更し,瞬時に移動した場合にキューの最先端に移動する.

変わる部分2

最良の場合、一つのことを見つけたら、できるだけ結果が出た瞬間にwhile文を直ちに修正して、逃げ出すようにします.

正しいコード

# 숨바꼭질 3 
# 숨바꼭질 2 
import sys
from collections import deque
input=sys.stdin.readline



N,K=map(int,input().split())


q=deque()
q.appendleft([N,0])# start , cnt 


visited=[0 for _ in range(100001)] 
while len(q)!=0:
    start,cnt=q.popleft()
    visited[start]=1
    
    if start==K:
        print(cnt)
        break
    else:
        # 답이 아닌 경우 
        if start-1>=0 and visited[start-1]==0:
            q.append([start-1,cnt+1])
        if start+1<=100000 and visited[start+1]==0:
            q.append([start+1,cnt+1])
        if start*2<=100000 and visited[start*2]==0:
            q.appendleft([start*2,cnt])

結果は正しい