পাইথনে বম ছাড়া নিরাপদ পথ খুঁজে বের করার প্রোগ্রাম

একটি আয়তাকার এলাকায় বম থাকা অবস্থায় নিচ থেকে উপরে একটি নিরাপদ সतত পথ খুঁজে বের করা হয়। প্রতিটি বমের অবস্থান [x, y, radius] আকারে দেওয়া থাকে। পথটি যেকোনো বমের সেফটি রেডিয়াসে داخل না হয়ে যেতে হবে।

ইনপুট উদাহরণ

mat = [[0, 1, 2], [3, 2, 1], [2, 1, 1]]
w = 4

আউটপুট: False (পথ খুঁজে পাওয়া যায়নি)

অ্যালগরিদম

1. insec() ফাংশন দিয়ে দুটি বমের ওভারল্যাপ চেক করুন (দূরত্ব ≤ রেডিয়াসের যোগফল)।
2. ম্যাট্রিক্সকে x-কোঅর্ডিনেট অনুযায়ী সর্ট করুন।
3. স্বীপ লাইন অ্যালগরিদম ব্যবহার করে বমগুলোর কভারেজ ইন্টারভাল মেটা রাখুন।
4. যদি কোনো সময় ইন্টারভাল পুরো প্রস্থ w কভার করে, তবে পথ সম্ভব নয় (False)।

পাইথন কোড

from bisect import bisect_left, insort

def insec(p, q):
    x1, y1, x2, y2 = p[1], p[2], q[1], q[2]
    r1, r2 = p[3], q[3]
    d = (x1 - x2)**2 + (y1 - y2)**2
    dec = (r1 + r2)**2
    return d <= dec

def solve(mat, w):
    mat.sort(key=lambda i: i[0] - i[2])
    temp = []
    if mat[0][0] - mat[0][2] > 0:
        return True
    for p, q, r in mat:
        min_wid, max_wid = p - r, p + r
        if len(temp) == 0:
            temp.append([p + r, p, q, r, p - r, p + r])
        else:
            mx = max(bisect_left(temp, [p - r, -p, q, r, 0, 0]) - 1, 0)
            in_list = [p + r, p, q, r, p - r, p + r]
            for i in range(mx, len(temp)):
                if insec(temp[i], in_list):
                    max_wid = max(max_wid, temp[i][-1])
                min_wid = min(min_wid, temp[i][-2])
            in_list[-2] = min_wid
            in_list[-1] = max_wid
            insort(temp, in_list)
        if min_wid <= 0 and max_wid >= w:
            return False
    return True

# টেস্ট
print(solve([[0, 1, 2], [3, 2, 1], [2, 1, 1]], 4))  # False

ব্যাখ্যা

প্রোগ্রামটি বমগুলোর নিরাপদ এলাকা বিবেচনা করে একটি গ্রাফ তৈরি করে এবং বাম থেকে ডানে পথ পাওয়া যায় কিনা তা চেক করে। সময় জটিলতা: O(n log n)।