पायथन में बम को छुए बिना आयताकार क्षेत्र में निरंतर पथ खोजने का प्रोग्राम

मान लीजिए हमें एक सरणी mat दी गई है जहां तत्व [p, q, r] के रूप में हैं, जहां p, q ज्यामितीय निर्देशांक हैं और r त्रिज्या मान है। सरणी में आइटम दिए गए चौड़ाई w के आयताकार क्षेत्र में बमों के स्थान हैं। आयत अनंत लंबा है और x निर्देशांक x = 0 से x = w तक सीमित है। बम की स्थिति में r मान बम की सुरक्षा त्रिज्या को दर्शाता है, अर्थात उस त्रिज्या से कम दूरी पर कुछ भी बम को संलग्न करेगा। इसलिए, हमें एक निरंतर पथ खींचना है जो हर बम के नीचे से शुरू होकर हर बम के ऊपर समाप्त होता है, बिना किसी बम को संलग्न किए। यदि हम यह रेखा खींच सकते हैं तो True प्रिंट करें, अन्यथा False प्रिंट करें।

इसलिए, यदि इनपुट है mat = [[0, 1, 2], [3, 2, 1], [2, 1, 1]], w = 4; तो आउटपुट होगा False।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• insec() फ़ंक्शन परिभाषित करें। यह p, q लेगा:
  • x1 := p[1], x2 := p[2]
  • y2 := q[1], y4 := q[2]
  • r1 := p[3], r2 := q[3]
  • d := (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
  • dec := (r1 + r2) * (r1 + r2)
  • यदि d <= dec तो True लौटाएं, अन्यथा False लौटाएं
• x निर्देशांक मानों के आधार पर मैट्रिक्स को सॉर्ट करें
• temp := एक नई सूची
• यदि mat[0][0] - mat[0][2] > 0, तो True लौटाएं
• mat में प्रत्येक p, q, r के लिए, करें:
  • min_wid := p - r
  • max_wid := p + r
  • यदि temp का आकार 0 के समान है, तो:
    • [p + r, p, q, r, p - r, p + r] वाली सूची को temp के अंत में जोड़ें
  • अन्यथा:
    • 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] वाली एक नई सूची
    • mx से temp के आकार तक i के लिए, करें:
      • यदि insec(temp[i], in_list) True है, तो:
        • max_wid = max(max_wid, temp[i, -1])
      • min_wid = min(min_wid, temp[i, -2])
    • in_list का अंतिम से दूसरा तत्व := min_wid
    • in_list का अंतिम तत्व := max_wid
    • in_list को क्रमबद्ध क्रम बनाए रखते हुए temp में डालें
  • यदि min_wid <= 0 और max_wid >= w, तो:
    • False लौटाएं
• True लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

from bisect import bisect_left, insort
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
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) * (x1 - x2) + (y1 - y2) * (y1 - y2)
    dec = (r1 + r2) * (r1 + r2)
    return d <= dec
print(solve([[0, 1, 2], [3, 2, 1], [2, 1, 1]], 4))

इनपुट

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

आउटपुट

False