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