用 Python 编写程序，找出从当前位置通过给定点是否可以到达某个点
pythonserver side programmingprogramming更新于 2026/1/11 17:16:17
假设在二维空间中，一个指针位于坐标为 (px, py) 的点 p。现在，指针必须移动到坐标为 (qx, qy) 的另一个点 q。指针不能自由移动，如果中间有一些点，它就可以移动到 q。我们给出了一个包含各种坐标点的点数组"路径"。如果某个点位于 (x+1, y) 或 (x, y+1) 或 (x-1, y) 或 (x, y-1)，则指针可以移动到该点。数组"路径"中的给定点必须按顺序连续处理，这意味着即使无法进行移动，也必须将数组中的每个点添加到总路径中。因此，给定起点和目标点，我们必须找出指针是否可以从给定的点到达目的地。如果可以，我们打印出它到达目的地所遍历的总点数；如果不能，我们打印 -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) 对的新集合
- 对于到达位置 k 的路径中的每个 x、y，执行
- 将 (x, y) 对添加到顶点
- trav:= 一个包含 (px, py) 对的新双端队列
- 当 trav 不为空时，执行
- 对 (x, y) := 从 trav 中弹出最左边的项目
- 如果 (x, y) 与 (qx, qy) 相同，则
- 返回 True
- 对于 ((x - 1, y),( x + 1, y), (x, y) 中的每个 kx、ky – 1), (x, y + 1)), do
- 如果对 (kx, ky) 存在于顶点中，则
- 在 trav 末尾插入对 (kx, ky)
- 从顶点中删除对 (kx, ky)
- 如果对 (kx, ky) 存在于顶点中，则
- 返回 False
- ll := -1
- ul := size of paths + 1
- 当 ll + 1 < ul 时，执行
- k := ll + ((ul - ll) / 2) 的底值
- 如果 helper(k) 为 True，则
- ul := k
- 否则，
- ll := k
- 如果 ul <= 路径大小则返回 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
