পাইথনে দেওয়া পয়েন্টগুলো দিয়ে গন্তব্য পৌঁছানো সম্ভব কিনা চেক করা

একটি ২ডি স্পেসে একটি পয়েন্টার দেওয়া পয়েন্টের সিকোয়েন্স অনুসরণ করে গন্তব্যে পৌঁছাতে পারে কিনা তা নির্ধারণ করা হয়। পয়েন্টার শুধু আড়াঢালে (আপ, ডাউন, লেফট, রাইট) যেতে পারে।

ইনপুট উদাহরণ

px=1, py=1, qx=2, qy=3
paths = [[1,2], [0,1], [0,2], [1,3], [3,3]]

আউটপুট: 4 (ট্রাভার্স করা পয়েন্টের সংখ্যা)

অ্যালগরিদম

1. বাইনারি সার্চ ব্যবহার করে সর্বনিম্ন পয়েন্ট সংখ্যা খুঁজুন যাতে গন্তব্যে পৌঁছানো যায়।
2. helper(k) ফাংশন প্রথম kটি পয়েন্ট ব্যবহার করে BFS চালায়।
3. যদি পৌঁছানো যায়, তবে ul = k, অন্যথায় ll = k।

পাইথন কোড

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

ব্যাখ্যা

বাইনারি সার্চ + BFS কাম্বিনেশন ব্যবহার করে অপ্টিমাল সময়ে সমাধান করা হয়েছে। সময় জটিলতা: O(N log N)।