Python程序：在矩形区域中寻找不触碰炸弹的连续路径

假设我们得到一个数组 mat，其中元素的形式为 [p, q, r]，其中 p、q 是几何坐标，r 是半径值。数组中的项是给定宽度 w 的矩形区域中炸弹的位置。矩形无限长，并以 x 坐标 x = 0 到 x = w 为界。炸弹位置中的 r 值表示炸弹的安全半径，这意味着小于炸弹半径的任何物体都会触碰它。因此，我们需要做的是绘制一条连续路径，该路径从每个炸弹下方开始，并在每个炸弹上方结束，而不触碰任何一个炸弹。如果我们可以绘制这条线，我们将打印 True，否则打印 False。

因此，如果输入类似于 mat =

012
321
211

，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，则
      • 在 temp 的末尾添加包含 (p + r, p, q, r, p - r, p + r) 的列表
    • 否则，
      • mx := (在保持排序顺序的情况下可以插入列表 [p - r, -p, q, r, 0, 0] 的 temp 中的位置 - 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))

输入

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

输出

False

更新于： 2021年10月16日

226 次查看

开启你的职业生涯

通过完成课程获得认证

开始学习
广告