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

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

เช่น ถ้าอินพุตเป็น mat = [[0, 1, 2], [3, 2, 1], [2, 1, 1]], w = 4 ผลลัพธ์จะเป็น False

ขั้นตอนการแก้ปัญหา

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