[伯俊]13549号鬼ごっこ3
6432 ワード
質問リンク
https://www.acmicpc.net/problem/13549
問題の説明
に答える
座標系
に感銘を与える
最初は何とか再帰的に、深く優先的に探索したり、DPで計算したりしたが、思い出せなかった.
ブラウズが必要な値は優先順位があるため、幅優先ブラウズが必要です
その後も関数を確立してみて、距離がゼロの座標を優先してすべてキューに入れてから、もう一つの座標を置く方法でインデックスが間違っていました.
コード#コード# from collections import deque
def bfs():
dist = [float('inf')] * 200000
dist[n] = 0
q = deque([n])
while q:
cn = q.popleft()
if cn == k:
return dist[cn]
for i in range(3):
nn = get_nn(cn, i)
if not (0 <= nn < len(dist)):
continue
if dist[nn] != float('inf'):
continue
if i == 0:
dist[nn] = dist[cn]
q.appendleft(nn)
else:
dist[nn] = dist[cn] + 1
q.append(nn)
def get_nn(cn, i):
if i == 0:
return cn * 2
if i == 1:
return cn + 1
return cn - 1
n, k = map(int, input().split())
print(bfs())
Reference
この問題について([伯俊]13549号鬼ごっこ3), 我々は、より多くの情報をここで見つけました
https://velog.io/@leehj8896/백준-13549번-숨바꼭질-3
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
from collections import deque
def bfs():
dist = [float('inf')] * 200000
dist[n] = 0
q = deque([n])
while q:
cn = q.popleft()
if cn == k:
return dist[cn]
for i in range(3):
nn = get_nn(cn, i)
if not (0 <= nn < len(dist)):
continue
if dist[nn] != float('inf'):
continue
if i == 0:
dist[nn] = dist[cn]
q.appendleft(nn)
else:
dist[nn] = dist[cn] + 1
q.append(nn)
def get_nn(cn, i):
if i == 0:
return cn * 2
if i == 1:
return cn + 1
return cn - 1
n, k = map(int, input().split())
print(bfs())Reference
この問題について([伯俊]13549号鬼ごっこ3), 我々は、より多くの情報をここで見つけました https://velog.io/@leehj8896/백준-13549번-숨바꼭질-3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol