找出从当前位置通过 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 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