pts라는 배열에 주어진 점 집합이 있다고 가정합니다. 또한 현재 위치인 또 다른 점(x, y)이 있습니다. 유효한 점을 현재 점과 동일한 x 좌표 또는 동일한 y 좌표를 공유하는 점으로 정의합니다. 현재 위치(x, y)에서 맨해튼 거리가 가장 작은 유효한 포인트의 인덱스를 반환해야 합니다. 포인트가 두 개 이상인 경우 인덱스가 가장 작은 유효한 포인트를 반환합니다. (참고:두 점 (a, b)와 (p, q) 사이의 맨해튼 거리는 |a - p| + |b - q|입니다.
따라서 입력이 pts =[(1,2),(3,1),(3,4),(2,3),(4,4)] pt =(2,4)와 같으면 두 개의 가장 가까운 점 (3,4) 및 (2,3)이 있기 때문에 출력은 2가 되지만 (3,4)의 인덱스는 더 작습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
x, y :=pt
-
idx :=-1
-
가장 작은 :=무한대
-
pt의 각 p에 대해 수행
-
p[0]이 x와 같거나 p[1]이 y와 같으면
-
거리 :=|x - p[0]| + |y - p[1]|
-
dist <가장 작은 경우
-
idx :=pts 단위의 p 인덱스
-
가장 작은 :=dist
-
-
그렇지 않으면 dist가 가장 작은 것과 같을 때
-
p의 인덱스가 pts
-
idx :=pts 단위의 p 인덱스
-
가장 작은 :=dist
-
-
-
-
-
IDx를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(pts, pt):
x, y = pt
idx = -1
smallest = float("inf")
for p in pts:
if p[0] == x or p[1] == y:
dist = abs(x - p[0]) + abs(y - p[1])
if dist < smallest:
idx = pts.index(p)
smallest = dist
elif dist == smallest:
if pts.index(p) < idx:
idx = pts.index(p)
smallest = dist
return idx
pts = [(1,2),(3,1),(3,4),(2,3),(4,4)]
pt = (2,4)
print(solve(pts, pt)) 입력
[(1,2),(3,1),(3,4),(2,3),(4,4)], (2,4)
출력
2