मान लीजिए हमारे पास 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) है, तो आउटपुट 2 होगा क्योंकि दो निकटतम बिंदु (3,4) और (2,3) हैं, लेकिन (3,4) का इंडेक्स छोटा है।
हल करने के चरण
x, y := pt
idx := -1
smallest := अनंत
pts में प्रत्येक p के लिए, करें
यदि p[0], x के समान है या p[1], y के समान है, तो
dist := |x - p[0]| + |y - p[1]|
यदि dist < smallest, तो
idx := pts में p का इंडेक्स
smallest := dist
अन्यथा जब dist, smallest के समान है, तो
यदि pts में p का इंडेक्स < idx, तो
idx := pts में p का इंडेक्स
smallest := 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
