数据结构
网络
关系数据库管理系统 (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 次查看
广告