資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Python程式：判斷點是否可達
假設在二維空間中，一個指標位於座標為(px, py)的點p。現在指標必須移動到另一個座標為(qx, qy)的點q。指標不能自由移動，只有當某些點位於兩者之間時，它才能移動到q。我們得到一個包含各種座標點的點陣列“paths”。如果指標位於當前位置的(x+1, y)或(x, y+1)或(x-1, y)或(x, y-1)處，則它可以移動到該點。陣列'paths'中給定的點必須按順序處理，這意味著即使無法移動，也必須將陣列中的每個點都新增到總路徑中。因此，給定起點和終點，我們必須找出指標是否可以從給定點到達終點。如果可以，我們輸出到達終點所經過的總點數；如果不能，則輸出-1。
因此，如果輸入類似於px = 1，py = 1，qx = 2，qy = 3，paths = [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]]，則輸出為4。
因此，如果我們按順序處理這些點，我們得到：
點(1, 2)：移動完成，當前指標位置(1, 2)。已遍歷點數：1。
點(0, 1)：未移動，當前指標位置(1, 2)。已遍歷點數：2。
點(0, 2)：未移動，當前指標位置(1, 2)。已遍歷點數：3。
點(1, 3)：移動完成，當前指標位置(1, 3)。已遍歷點數：4。
終點位於當前指標位置的(x+1, y)處，因此已遍歷的總點數為4。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式helper()。它將接收k
- vertices := 一個包含(px, py)和(qx, qy)對的新集合
- 對於paths中直到位置k的每個x, y：
- 將(x, y)對新增到vertices
- trav:=一個包含(px, py)對的新雙端佇列
- 當trav非空時：
- pair (x, y) := 從trav的左側彈出專案
- 如果(x, y)與(qx, qy)相同，則
- 返回True
- 對於每個kx, ky in ((x - 1, y),( x + 1, y), (x, y – 1), (x, y + 1))：
- 如果(kx, ky)對存在於vertices中，則
- 將(kx, ky)對插入到trav的末尾
- 從vertices中刪除(kx, ky)對
- 如果(kx, ky)對存在於vertices中，則
- 返回False
- ll := -1
- ul := paths的大小 + 1
- 當ll + 1 < ul時：
- k := ll + floor((ul - ll) / 2)
- 如果helper(k)為True，則
- ul := k
- 否則，
- ll := k
- 如果ul <= paths的大小，則返回ul，否則返回-1
示例
讓我們看看下面的實現來更好地理解：
from collections import deque
def solve(px, py, qx, qy, paths):
def helper(k):
vertices = {(px, py), (qx, qy)}
for x, y in paths[:k]:
vertices.add((x, y))
trav = deque([(px, py)])
while trav:
x, y = trav.popleft()
if (x, y) == (qx, qy):
return True
for kx, ky in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
if (kx, ky) in vertices:
trav.append((kx, ky))
vertices.remove((kx, ky))
return False
ll, ul = -1, len(paths) + 1
while ll + 1 < ul:
k = ll + (ul - ll) // 2
if helper(k):
ul = k
else:
ll = k
return ul if ul <= len(paths) else -1
print(solve(1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]))輸入
1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]
輸出
4
更新於：2021年10月16日
241 次檢視
廣告