파이썬에서 주어진 포인트를 통해 현재 위치에서 도달할 수 있는 포인트인지 알아내는 프로그램

<시간/>

2D 공간에서 포인터가 좌표(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, 경로 =[[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]], 출력은 4가 됩니다.

따라서 포인트를 직렬로 처리하면 다음을 얻습니다. -

Point (1, 2):이동, 현재 포인터 위치 (1, 2). 통과한 포인트:1.

포인트(0, 1):이동하지 않고 현재 포인터 위치(1, 2)입니다. 통과한 포인트:2.

포인트(0, 2):이동하지 않고 현재 포인터 위치(1, 2)입니다. 통과한 포인트:3.

Point (1, 3):이동, 현재 포인터 위치 (1, 3). 통과한 포인트:4.

목적지는 현재 포인터 위치에서 (x+1, y) 위치에 있으므로 이동한 총 포인트 수는 4입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

helper() 함수를 정의합니다. 이것은 k
- vertices :=(px, py) 및 (qx, qy) 쌍을 포함하는 새로운 세트
- k 위치까지의 경로에 있는 각 x, y에 대해 do
  - 꼭짓점에 쌍(x, y) 추가
- trav:=(px, py) 쌍을 포함하는 새로운 데크
- trav가 비어 있지 않은 동안 do
  - pair (x, y) :=trav에서 가장 왼쪽 항목 팝
  - (x, y)가 (qx, qy)와 같으면
    - 참 반환
  - 각 kx, ky in ((x - 1, y),( x + 1, y), (x, y – 1), (x, y + 1)), do
    - (kx, ky) 쌍이 꼭짓점에 있으면
      - trav 끝에 쌍(kx, ky) 삽입
      - 꼭짓점에서 쌍(kx, ky) 삭제
  - 거짓을 반환
ll :=-1
ul :=경로 크기 + 1
ll + 1
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]]