用 Python 编写程序，在矩形区域内找到一条不与炸弹接触的连续路径

pythonserver side programmingprogramming更新于 2026/1/11 17:48:17

假设我们得到一个数组 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

，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 := a new list
如果 mat[0][0] -垫[0][2]> 0，则
- 返回 True
对于 mat 中的每个 p、q、r，执行
- min_wid := p - r
- max_wid := p + r
- 如果 temp 的大小与 0 相同，则
  - 在 temp 末尾添加包含 (p + r, p, q, r, p - r, p + r) 的列表
- 否则，
  - mx := (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_wid, temp[i, -1]) 的最大值
    - min_wid = (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))