โปรแกรมค้นหาคือจุดที่สามารถเข้าถึงได้จากตำแหน่งปัจจุบันผ่านจุดที่กำหนดในPython

สมมติว่าในพื้นที่ 2D ตัวชี้อยู่ที่จุด p ที่มีพิกัด (px, py) ตอนนี้ตัวชี้ต้องย้ายไปยังจุดอื่น q ที่มีพิกัด (qx, qy) ตัวชี้ไม่สามารถเคลื่อนที่ได้อย่างอิสระ สามารถเดินทางไปยัง q ได้หากมีบางจุดอยู่ระหว่างนั้น เราได้รับอาร์เรย์ของ "เส้นทาง" ของจุดที่ประกอบด้วยจุดพิกัดต่างๆ ตัวชี้สามารถย้ายไปยังจุดที่อยู่ที่ (x+1, y) หรือ (x, y+1) หรือ (x-1, y) หรือ (x, y-1) จากตำแหน่งปัจจุบันของตัวชี้ . จุดที่กำหนดใน 'เส้นทาง' ของอาร์เรย์ต้องได้รับการประมวลผลตามลำดับ ซึ่งหมายความว่าแต่ละจุดในอาร์เรย์จะต้องถูกเพิ่มเข้าไปในเส้นทางทั้งหมด แม้ว่าจะไม่สามารถทำการย้ายได้ ดังนั้น จากจุดเริ่มต้นและปลายทาง เราต้องค้นหาว่าตัวชี้สามารถไปถึงปลายทางจากจุดที่กำหนดได้หรือไม่ หากทำได้ เราจะพิมพ์จำนวนคะแนนทั้งหมดที่ผ่านเพื่อไปยังปลายทาง และถ้ามันไม่สามารถให้เราพิมพ์ -1.

ดังนั้น หากอินพุตเป็น px =1, py =1, qx =2, qy =3, paths =[[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]] จากนั้นผลลัพธ์จะเป็น 4

ดังนั้น หากเราประมวลผลคะแนนตามลำดับ เราจะได้ -

จุด (1, 2):ย้ายแล้ว ตำแหน่งตัวชี้ปัจจุบัน (1, 2) คะแนนที่ข้ามไป:1.

จุด (0, 1):ไม่มีการเคลื่อนไหว ตำแหน่งตัวชี้ปัจจุบัน (1, 2) คะแนนที่ข้ามไป:2.

จุด (0, 2):ไม่มีการเคลื่อนไหว ตำแหน่งตัวชี้ปัจจุบัน (1, 2) คะแนนที่ข้ามไป:3.

จุด (1, 3):ย้ายแล้ว ตำแหน่งตัวชี้ปัจจุบัน (1, 3) คะแนนที่ข้ามไป:4.

ปลายทางอยู่ที่ตำแหน่ง (x+1, y) จากตำแหน่งตัวชี้ปัจจุบัน ดังนั้นจำนวนจุดที่ข้ามทั้งหมดคือ 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน helper() นี่จะใช้เวลา k
  • จุดยอด :=ชุดใหม่ที่มีคู่ (px, py) และ (qx, qy)
  • สำหรับแต่ละ x, y ในเส้นทางที่ไม่เกินตำแหน่ง k, do
    • เพิ่มคู่ (x, y) ให้กับจุดยอด
  • trav:=deque ใหม่ที่มีคู่ (px, py)
  • ในขณะที่ trav ไม่ว่างเปล่า ทำ
    • คู่ (x, y) :=ป๊อปรายการซ้ายสุดจาก trav
    • ถ้า (x, y) เหมือนกับ (qx, qy) แล้ว
      • คืนค่า True
    • สำหรับแต่ละ kx, ky in ((x - 1, y),( x + 1, y), (x, y – 1), (x, y + 1)), do
      • ถ้าคู่ (kx, ky) มีอยู่ในจุดยอด แล้ว
        • ใส่คู่ (kx, ky) ที่ส่วนท้ายของ trav
        • ลบคู่ (kx, ky) ออกจากจุดยอด
    • คืนค่าเท็จ
• ll :=-1
• ul :=ขนาดของเส้นทาง + 1
• ในขณะที่ ll + 1
  • k :=ll + ค่าพื้นของ ((ul - ll) / 2)
  • ถ้า helper(k) เป็น True แล้ว
    • ul :=k
  • มิฉะนั้น
    • ll :=k
• ส่งคืน ul ถ้า ul <=ขนาดของเส้นทาง มิฉะนั้น ให้คืนค่า -1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

4