[伯俊/Python]5014リンク開始

https://www.acmicpc.net/problem/5014

アルゴリズム分類

BFS

問題を解く

スタート地点から、上がれば上がる、降りれば降りる.
アクセスは、二次数値にアクセスしたことがない場合にのみ挿入されます.
ex)
deque([3])
[0, 1, 0, 2, 0, 0, 0, 0, 0, 0, 0]
1
deque([5, 2])
[0, 1, 3, 2, 0, 3, 0, 0, 0, 0, 0]
3
deque([2, 7, 4])
[0, 1, 3, 2, 4, 3, 0, 4, 0, 0, 0]
5
deque([7, 4])
[0, 1, 3, 2, 4, 3, 0, 4, 0, 0, 0]
2
deque([4, 9, 6])
[0, 1, 3, 2, 4, 3, 5, 4, 0, 5, 0]
7
deque([9, 6])
[0, 1, 3, 2, 4, 3, 5, 4, 0, 5, 0]
4
deque([6, 8])
[0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 0]
9
deque([8])
[0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 0]
6
deque([10])
[0, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7]
8
そして、到着地点に対応する値(回数-1であるため)を出力する.

ソースコード

from collections import deque

def bfs():
  queue=deque()
  queue.append(s)
  visited[s]=1
  
  while queue:
    now=queue.popleft()
    if now==g:
      return visited[g]

    up=now+u
    down=now-d 
    if up<=f and not visited[up]:
      visited[up]=visited[now]+1
      queue.append(up)
    if down>=1 and not visited[down]:
      visited[down]=visited[now]+1
      queue.append(down)

  return -1

f,s,g,u,d=list(map(int, input().split()))
visited=[0 for _ in range(f+1)]

result=bfs()
if result!=-1:
  print(result-1)
else:
  print("use the stairs")

 참고: https://deok2kim.tistory.com/148