โปรแกรมหาเส้นทางเป็นเส้นทางต่อเนื่องในพื้นที่สี่เหลี่ยมโดยไม่ต้องวางระเบิดในPython

สมมติว่าเราได้รับแผ่นอาร์เรย์ที่องค์ประกอบอยู่ในรูปแบบนี้ [p, q, r] โดยที่ p, q คือพิกัดทางเรขาคณิตและ r คือค่ารัศมี รายการในอาร์เรย์คือตำแหน่งของระเบิดในพื้นที่สี่เหลี่ยมที่มีความกว้างที่กำหนด w สี่เหลี่ยมผืนผ้ายาวเป็นอนันต์และล้อมรอบด้วยพิกัด x x =0 ถึง x =w ค่า r ในตำแหน่งระเบิดหมายถึงรัศมีความปลอดภัยของระเบิด หมายความว่าอะไรก็ตามที่น้อยกว่ารัศมีของระเบิดจะเข้าปะทะ ดังนั้น สิ่งที่เราต้องทำคือการวาดเส้นทางต่อเนื่องที่เริ่มต้นจากด้านล่างของระเบิดทุกอันและสิ้นสุดเหนือระเบิดทุกอันโดยไม่เข้าไปยุ่งกับพวกมัน เราจะพิมพ์ True หากวาดเส้นนี้ได้ มิฉะนั้น เราจะพิมพ์ False

ดังนั้นหากอินพุตเป็นเหมือน mat =

, w =4; แล้วผลลัพธ์จะเป็นเท็จ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน 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)
  • ธันวา :=(r1 + r2) *(r1 + r2)
  • คืนค่า True ถ้า d <=dec มิฉะนั้นคืนค่า False
• จัดเรียงเมทริกซ์ตามค่าพิกัด x
• temp :=รายการใหม่
• ถ้า mat[0][0] - mat[0][2]> 0 แล้ว
  • คืนค่า True
• สำหรับแต่ละ p, q, r ใน mat ทำ
  • min_wid :=p - r
  • max_wid :=p + r
  • ถ้าขนาดอุณหภูมิเท่ากับ 0 แล้ว
    • เพิ่มรายการที่มี (p + r, p, q, r, p - r, p + r) ที่ส่วนท้ายของอุณหภูมิ
  • มิฉะนั้น
    • mx :=maximum of (ตำแหน่งใน temp ที่สามารถแทรกรายการ [p - r, -p, q, r, 0, 0] เพื่อรักษาลำดับการเรียงลำดับ - 1) , 0
    • in_list :=รายการใหม่ที่มีองค์ประกอบ (p + r, p, q, r, p - r, p + r)
    • สำหรับฉันในช่วง mx ถึงขนาดของอุณหภูมิ ให้ทำ
      • ถ้า insec(temp[i], in_list) เป็น True แล้ว
        • max_wid =สูงสุดของ (max_wid, temp[i, -1])
      • min_wid =ขั้นต่ำของ (min_wid, temp[i, -2])
    • องค์ประกอบสุดท้ายที่สองของ in_list :=min_wid
    • last_element ของ in_list :=max_wid
    • แทรก in_list ชั่วคราวเพื่อรักษาลำดับการจัดเรียง
  • ถ้า min_wid <=0 และ max_wid>=w แล้ว
    • คืนค่าเท็จ
• คืนค่า 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