Chương trình để tìm ra một điểm có thể truy cập được từ vị trí hiện tại thông qua các điểm đã cho trong Python

Giả sử trong không gian 2D, một con trỏ nằm tại điểm p có tọa độ (px, py). Bây giờ con trỏ phải di chuyển đến một điểm q khác có tọa độ (qx, qy). Con trỏ không thể di chuyển tự do, nó có thể di chuyển đến q nếu có một số điểm nằm ở giữa. Chúng ta được cung cấp một mảng "đường dẫn" điểm chứa các điểm tọa độ khác nhau. Con trỏ có thể di chuyển đến một điểm nếu nó nằm tại (x + 1, y) hoặc (x, y + 1) hoặc (x-1, y) hoặc (x, y-1) từ vị trí hiện tại của con trỏ . Các điểm đã cho trong 'đường dẫn' của mảng phải được xử lý tuần tự theo thứ tự, có nghĩa là mỗi điểm trong mảng phải được cộng vào tổng đường dẫn ngay cả khi không thể di chuyển. Vì vậy, với điểm xuất phát và điểm đến, chúng ta phải tìm xem liệu con trỏ có thể đến đích từ những điểm đã cho hay không. Nếu có thể, chúng tôi in ra tổng số điểm mà nó đã đi qua để đến đích; và nếu nó không thể, chúng tôi in -1.

Vì vậy, nếu đầu vào giống như px =1, py =1, qx =2, qy =3, path =[[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]], thì đầu ra sẽ là 4.

Vì vậy, nếu chúng tôi xử lý các điểm theo thứ tự, chúng tôi nhận được -

Point (1, 2):Di chuyển được thực hiện, vị trí con trỏ hiện tại (1, 2). Số điểm đã duyệt:1.

Điểm (0, 1):Không di chuyển được, vị trí con trỏ hiện tại (1, 2). Số điểm đã duyệt:2.

Điểm (0, 2):Không di chuyển được, vị trí con trỏ hiện tại (1, 2). Số điểm đã duyệt qua:3.

Point (1, 3):Di chuyển được thực hiện, vị trí con trỏ hiện tại (1, 3). Số điểm đã duyệt qua:4.

Điểm đến được đặt tại vị trí (x + 1, y) từ vị trí con trỏ hiện tại, vì vậy tổng số điểm được duyệt qua là 4.

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

• Xác định một hàm trợ giúp (). Điều này sẽ mất k
  • đỉnh:=một tập hợp mới chứa các cặp (px, py) và (qx, qy)
  • đối với mỗi x, y trong các đường dẫn đến vị trí k, thực hiện
    • thêm cặp (x, y) vào các đỉnh
  • trav:=một cặp chứa deque mới (px, py)
  • trong khi trav không trống, hãy thực hiện
    • cặp (x, y):=bật mục ngoài cùng bên trái khỏi trav
    • nếu (x, y) giống với (qx, qy) thì
      • trả về True
    • đối với mỗi kx, ky in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)), thực hiện
      • nếu cặp (kx, ky) hiện diện trong các đỉnh, thì
        • chèn cặp (kx, ky) vào cuối trav
        • xóa cặp (kx, ky) khỏi các đỉnh
    • trả về Sai
• ll:=-1
• ul:=kích thước của đường dẫn + 1
• while ll + 1
• k:=ll + giá trị sàn của ((ul - ll) / 2)
• nếu helper (k) là True, thì
  • ul:=k
• nếu không,
  • ll:=k

Ví dụ

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

from collections import deque
def solve(px, py, qx, qy, paths):
   def helper(k):
      vertices = {(px, py), (qx, qy)}
      for x, y in paths[:k]:
         vertices.add((x, y))
      trav = deque([(px, py)])
      while trav:
         x, y = trav.popleft()
         if (x, y) == (qx, qy):
            return True
         for kx, ky in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            if (kx, ky) in vertices:
               trav.append((kx, ky))
               vertices.remove((kx, ky))
      return False
   ll, ul = -1, len(paths) + 1
   while ll + 1 < ul:
      k = ll + (ul - ll) // 2
      if helper(k):
         ul = k
      else:
         ll = k
   return ul if ul <= len(paths) else -1

print(solve(1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]))

Đầu vào

1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]

Đầu ra

4