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）进行了新设置
  • 对于每个到位置k的路径中的x，y，执行以下操作
    • 将对（x，y）添加到vertices中
  • trav：包含对（px，py）进行了新设置
  • while trav不为空，执行以下操作
    • 从左侧最左边的项弹出对（x，y）
    • 如果（x，y）与（qx，qy）相同，则
    • 返回True
    • 对于（（x-1，y），（x+1，y），（x，y-1），（x，y+1））中的每个kx，ky，执行以下操作
    • 如果vertices中存在对（kx，ky），则
      • 在trav的末尾插入对（kx，ky）
      • 从vertices中删除对（kx，ky）
    • 返回False
• ll：= -1
• ul：=路径大小+1
• 当ll+1 < ul时，执行以下操作
  • 如果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