Chương trình kiểm tra điểm đích có thể đến được từ điểm xuất phát qua các điểm trung gian Python

Trong không gian 2D, con trỏ bắt đầu tại điểm p(px, py) và cần di chuyển đến điểm q(qx, qy). Con trỏ chỉ có thể di chuyển đến các điểm lân cận theo 4 hướng: (x+1, y), (x, y+1), (x-1, y), (x, y-1). Cho mảng paths chứa các điểm trung gian, phải xử lý theo thứ tự. Trả về số điểm đã duyệt nếu đến được đích, ngược lại trả về -1.

Ví dụ: px=1, py=1, qx=2, qy=3, paths=[[1,2],[0,1],[0,2],[1,3],[3,3]] → kết quả 4.

Giải thuật

1. Sử dụng tìm kiếm nhị phân (binary search) trên số điểm trung gian cần dùng
2. Hàm helper(k) kiểm tra xem có đường đi từ p đến q dùng k điểm đầu tiên của paths không (BFS)
3. Thu hẹp khoảng tìm kiếm để tìm k nhỏ nhất

Ví dụ triển khai

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