白俊12851号鬼ごっこ2派SUN
10331 ワード
質問する
インプット
solution import sys
from collections import deque
input = sys.stdin.readline
Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
res = 0
if n == m:
res = 1
while dq:
a = dq.popleft()
if a * 2 < Max:
if dis[a * 2] == -1:
dq.append(a * 2)
dis[a * 2] = dis[a] + 1
elif dis[a * 2] == dis[a] + 1:
dq.append(a * 2)
if a * 2 == m and dis[a] + 1 == dis[m]:
res += 1
if a + 1 < Max:
if dis[a + 1] == -1:
dq.append(a + 1)
dis[a + 1] = dis[a] + 1
elif dis[a + 1] == dis[a] + 1:
dq.append(a + 1)
if a + 1 == m and dis[a] + 1 == dis[m]:
res += 1
if a - 1 >= 0:
if dis[a - 1] == -1:
dq.append(a - 1)
dis[a - 1] = dis[a] + 1
elif dis[a - 1] == dis[a] + 1:
dq.append(a - 1)
if a - 1 == m and dis[a] + 1 == dis[m]:
res += 1
print(dis[m])
print(res)
説明:
キー(Key)
solution import sys
from collections import deque
input = sys.stdin.readline
Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
res = 0
if n == m:
res = 1
while dq:
a = dq.popleft()
if a * 2 < Max:
if dis[a * 2] == -1:
dq.append(a * 2)
dis[a * 2] = dis[a] + 1
elif dis[a * 2] == dis[a] + 1:
dq.append(a * 2)
if a * 2 == m and dis[a] + 1 == dis[m]:
res += 1
if a + 1 < Max:
if dis[a + 1] == -1:
dq.append(a + 1)
dis[a + 1] = dis[a] + 1
elif dis[a + 1] == dis[a] + 1:
dq.append(a + 1)
if a + 1 == m and dis[a] + 1 == dis[m]:
res += 1
if a - 1 >= 0:
if dis[a - 1] == -1:
dq.append(a - 1)
dis[a - 1] = dis[a] + 1
elif dis[a - 1] == dis[a] + 1:
dq.append(a - 1)
if a - 1 == m and dis[a] + 1 == dis[m]:
res += 1
print(dis[m])
print(res)
説明:
キー(Key)
import sys
from collections import deque
input = sys.stdin.readline
Max = 100001
n, m = map(int, input().split())
dq = deque()
dq.append(n)
dis = [-1 for _ in range(Max)]
dis[n] = 0
res = 0
if n == m:
res = 1
while dq:
a = dq.popleft()
if a * 2 < Max:
if dis[a * 2] == -1:
dq.append(a * 2)
dis[a * 2] = dis[a] + 1
elif dis[a * 2] == dis[a] + 1:
dq.append(a * 2)
if a * 2 == m and dis[a] + 1 == dis[m]:
res += 1
if a + 1 < Max:
if dis[a + 1] == -1:
dq.append(a + 1)
dis[a + 1] = dis[a] + 1
elif dis[a + 1] == dis[a] + 1:
dq.append(a + 1)
if a + 1 == m and dis[a] + 1 == dis[m]:
res += 1
if a - 1 >= 0:
if dis[a - 1] == -1:
dq.append(a - 1)
dis[a - 1] = dis[a] + 1
elif dis[a - 1] == dis[a] + 1:
dq.append(a - 1)
if a - 1 == m and dis[a] + 1 == dis[m]:
res += 1
print(dis[m])
print(res)
キー(Key)
BFSをすれば正解があるようです.
Reference
この問題について(白俊12851号鬼ごっこ2派SUN), 我々は、より多くの情報をここで見つけました https://velog.io/@slbin-park/백준-12851번-숨바꼭질-2-파이썬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol