找出从当前位置通过 Python 中的给定点可以到达的点的程序
假设在 2D 空间中，指针位于具有坐标 (px, py) 的点 p。现在指针必须移动到另一个具有坐标 (qx, qy) 的点 q。指针不能自由移动，如果中间有一些点，它可以移动到 q。我们得到了一个包含各种坐标点的点“路径”数组。指针可以移动到从指针当前位置(x+1, y) or (x, y+1) or (x-1, y) or (x, y-1) 的点. 数组“路径”中的给定点必须按顺序连续处理，这意味着即使无法进行移动，数组中的每个点也必须加到总路径中。因此，给定起点和终点，我们必须找出指针是否可以从给定的点到达目的地。如果可以的话 我们打印出它到达目的地所经过的总点数；如果不能，我们打印-1。
所以，如果输入像 px = 1, py = 1, qx = 2, qy = 3, paths = [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]]，则输出为 4。
所以，如果我们连续处理这些点，我们会得到 -
Point (1, 2)：进行移动，当前指针位置 (1, 2)。穿越点：1。
Point (0, 1)：没有移动，当前指针位置(1, 2)。遍历点数：2。
Point (0, 2)：没有移动，当前指针位置(1, 2)。遍历点数：3。
Point (1, 3)：进行移动，当前指针位置 (1, 3)。遍历点数：4。
目的地位于距离当前指针位置（x+1，y）处，所以遍历的总点数为4。
示例
让我们看看以下实现以获得更好的理解 -
from collections import dequedef 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
以上是 找出从当前位置通过 Python 中的给定点可以到达的点的程序 的全部内容， 来源链接： utcz.com/z/327366.html
