시작 위치 p에 있다고 가정하면 d1 및 d2 단위의 모든 방향(왼쪽 또는 오른쪽)으로 점프할 수 있습니다. p에서 점프하여 위치 q에 도달하는 데 필요한 최소 단계 수를 찾아야 합니다.
따라서 입력이 p =5, q =10, d1 =4, d2 =3과 같으면 거리 4를 두 번 사용하여 오른쪽으로 점프한 다음 위치 13에 도달한 다음 왼쪽으로 점프할 수 있으므로 출력은 3이 됩니다. 10에 도달하려면 3단위가 필요합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- gcd_res :=d1 및 d2의 gcd
- (p - q)가 gcd_res로 나누어지지 않으면
- 반환 -1
- que :=하나의 이중 종료 대기열 정의
- 방문함:=새로운 세트
- 대기열에 쌍(p, 0) 삽입
- p를 방문한 것으로 표시
- que> 0의 크기가 0이 아닌 동안 do
- (point, step) :=대기열의 앞 요소 및 대기열에서 삭제
- 포인트가 q와 같으면
- 반환 단계
- point + d1을 방문하지 않으면
- 한 쌍(point + d1, step + 1)을 que에 삽입
- (포인트 + d1) 방문으로 표시
- 방문하지 않은 point + d2가 0이 아니면
- 한 쌍(point + d2, step + 1)을 que에 삽입
- (포인트 + d2)를 방문한 것으로 표시
- 점 - 방문하지 않은 d1이 0이 아닌 경우
- 한 쌍(포인트 - d1, 단계 + 1)을 que에 삽입
- (포인트 - d1) 방문으로 표시
- point - 방문하지 않은 d2가 0이 아닌 경우
- 한 쌍(point - d2, step + 1)을 que에 삽입
- (포인트 - d2)를 방문한 것으로 표시
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import gcd from collections import deque def solve(p, d1, d2, q): gcd_res = gcd(d1, d2) if (p - q) % gcd_res != 0: return -1 que = deque() visited = set() que.appendleft([p, 0]) visited.add(p) while len(que) > 0: pair = que.pop() point, step = pair[0], pair[1] if point == q: return step if point + d1 not in visited: que.appendleft([(point + d1), step + 1]) visited.add(point + d1) if point + d2 not in visited: que.appendleft([(point + d2), step + 1]) visited.add(point + d2) if point - d1 not in visited: que.appendleft([(point - d1), step + 1]) visited.add(point - d1) if point - d2 not in visited: que.appendleft([(point - d2), step + 1]) visited.add(point - d2) p = 5 q = 10 d1 = 4 d2 = 3 print(solve(p, d1, d2, q))
입력
5, 4, 3, 10
출력
True