資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：在矩形區域中尋找不觸碰炸彈的連續路徑
假設我們得到一個數組 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，則
- 在 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] 之間的最小值
- 如果 insec(temp[i], in_list) 為 True，則
- 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 次檢視
廣告