Kiểm tra xem có thể đạt đến một số hay không bằng cách thực hiện các bước nhảy có độ dài nhất định trong Python

Giả sử chúng ta đang ở vị trí bắt đầu p, chúng ta có thể nhảy theo bất kỳ hướng nào (trái hoặc phải) đơn vị d1 và d2. Chúng ta phải tìm số bước tối thiểu cần thiết để đạt được ở vị trí q bằng cách nhảy từ p.

Vì vậy, nếu đầu vào là p =5, q =10, d1 =4, d2 =3, thì đầu ra sẽ là 3 vì chúng ta có thể nhảy sang phải bằng cách sử dụng khoảng cách 4 hai lần thì chúng ta có thể đến vị trí 13, sau đó nhảy sang trái 3 đơn vị để đạt 10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• gcd_res:=gcd của d1 và d2
• nếu (p - q) không chia hết cho gcd_res thì
  • trả về -1
• que:=xác định một hàng đợi kết thúc kép
• đã thăm:=một tập hợp mới
• chèn một cặp (p, 0) vào hàng đợi
• đánh dấu p là đã ghé thăm
• trong khi kích thước của que> 0 là khác 0, hãy thực hiện
  • (point, step):=phần tử phía trước của hàng đợi và xóa nó khỏi hàng
  • nếu điểm giống với q, thì
    • quay lại bước
  • nếu điểm + d1 không được truy cập, thì
    • chèn một cặp (điểm + d1, bước + 1) vào hàng đợi
    • đánh dấu (điểm + d1) là đã truy cập
  • nếu điểm + d2 không được truy cập là khác 0, thì
    • chèn một cặp (điểm + d2, bước + 1) vào hàng đợi
    • đánh dấu (điểm + d2) là đã truy cập
  • nếu điểm - d1 không được truy cập là khác 0, thì
    • chèn một cặp (điểm - d1, bước + 1) vào hàng đợi
    • đánh dấu (điểm - d1) là đã truy cập
  • nếu điểm - d2 không được truy cập là khác 0, thì
    • chèn một cặp (điểm - d2, bước + 1) vào hàng đợi
    • đánh dấu (điểm - d2) là đã truy cập

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

5, 4, 3, 10

Đầu ra

True