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

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

เช่น ถ้าอินพุตคือ px = 1, py = 1, qx = 2, qy = 3, paths = [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]] ผลลัพธ์จะเป็น 4

ขั้นตอนการแก้ปัญหา

1. กำหนดฟังก์ชัน helper(k):
   • vertices := เซตใหม่ที่มีคู่ (px, py) และ (qx, qy)
   • สำหรับแต่ละ x, y ใน paths จนถึงตำแหน่ง k เพิ่มคู่ (x, y) เข้า vertices
   • trav := deque ใหม่ที่มีคู่ (px, py)
   • ในขณะที่ trav ไม่ว่าง:
     • นำคู่ (x, y) ออกจากด้านซ้ายของ trav
     • ถ้า (x, y) เท่ากับ (qx, qy) คืนค่า True
     • สำหรับแต่ละ kx, ky ใน ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
       • ถ้าคู่ (kx, ky) อยู่ใน vertices ให้เพิ่มเข้า trav และลบออกจาก vertices
   • คืนค่า False
2. ll := -1, ul := ขนาดของ paths + 1
3. ในขณะที่ ll + 1 < ul:
   • k := ll + floor((ul - ll) / 2)
   • ถ้า helper(k) เป็น True ให้ ul := k มิฉะนั้น ll := k
4. คืนค่า ul ถ้า ul <= ขนาดของ paths มิฉะนั้น -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