白俊12851号:鬼ごっこ2

8266 ワード
python BFS ps テキストリンク

かくれんぼをする


白俊12851号:鬼ごっこ2

アイデア


これはかくれんぼをする題を少し応用した問題です.最速時間内に見つかった場合は、数を見つけます.キューを入れる条件を変更しました.
本来、次の場所に格納されている値が0の場合(アクセスしたことがない)、キューに格納されます.この問題では、次の場所に格納されている値が現在の場所に格納されている値よりも大きくても、(これは、その位置に到達するのに要する時間が同じであることを意味します.次の位置に格納される値が現在の位置に格納される値よりも小さい場合、より効果的な方法でその位置に到達することができます.)キューに入れました.
import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().split())
pos = [0] * 100001

def solve(start, end):
    q = deque()
    q.append(start)
    while q:
        x = q.popleft()
        if x == K:
            print(pos[x])
            break
        if x - 1 >= 0 and (pos[x - 1] == 0 or pos[x - 1] > pos[x]):
            pos[x - 1] = pos[x] + 1
            q.append(x - 1)
        if x + 1 <= 100000 and (pos[x + 1] == 0 or pos[x + 1] > pos[x]):
            pos[x + 1] = pos[x] + 1
            q.append(x + 1)
        if x * 2 <= 100000 and (pos[x * 2] == 0 or pos[x * 2] > pos[x]):
            pos[x * 2] = pos[x] + 1
            q.append(x * 2)
    ans = 1
    while q:
        x = q.popleft()
        if x == K:
            ans += 1
    print(ans)

solve(N, K)

おしゃべり


私たちは隠れん坊を全部解かなければならない.
Linuxはデータベースのタイミングバックアップを実現
nginx設定