ধরুন আমাদের একটি বিন্যাসে দেওয়া পয়েন্টের একটি সেট আছে যার নাম 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
-
ক্ষুদ্রতম :=অসীম
-
প্রতিটি p এর জন্য pts, করুন
-
যদি p[0] x এর মত হয় অথবা p[1] y এর মত হয়, তাহলে
-
dist :=|x - p[0]| + |y - p[1]|
-
যদি dist <সবচেয়ে ছোট, তাহলে
-
idx :=p এর index in pts
-
ক্ষুদ্রতম :=dist
-
-
অন্যথায় যখন দূরত্ব সবচেয়ে ছোট হিসাবে একই হয়, তখন
-
যদি p এর সূচী pts
-
idx :=p এর index in pts
-
ক্ষুদ্রতম :=dist
-
-
-
-
-
রিটার্ন আইডিএক্স
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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
