পাইথনে প্রদত্ত পয়েন্টের মাধ্যমে বর্তমান অবস্থান থেকে একটি বিন্দু পৌঁছানো যায় কিনা তা খুঁজে বের করার প্রোগ্রাম

ধরুন একটি 2D স্পেসে একটি পয়েন্টার p বিন্দুতে অবস্থিত যার স্থানাঙ্ক রয়েছে (px, py)। এখন পয়েন্টারকে স্থানাঙ্ক (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, paths =[[1, 2], [0, 1], [0, 2], [1, 3], [৩, ৩]], তাহলে আউটপুট হবে ৪।

সুতরাং, যদি আমরা পয়েন্টগুলিকে ক্রমিকভাবে প্রক্রিয়া করি, আমরা −

পাব

পয়েন্ট (1, 2):সরানো হয়েছে, বর্তমান পয়েন্টার অবস্থান (1, 2)। বিন্দু অতিক্রম করা হয়েছে:1.

পয়েন্ট (0, 1):কোন সরানো হয় না, বর্তমান পয়েন্টার অবস্থান (1, 2)। বিন্দু অতিক্রম করা হয়েছে:2.

পয়েন্ট (0, 2):কোন সরানো হয় না, বর্তমান পয়েন্টার অবস্থান (1, 2)। বিন্দু অতিক্রম করেছে:3.

পয়েন্ট (1, 3):সরানো হয়েছে, বর্তমান পয়েন্টার অবস্থান (1, 3)। বিন্দু অতিক্রম করা হয়েছে:4.

গন্তব্যটি বর্তমান পয়েন্টার অবস্থান থেকে (x+1, y) অবস্থানে অবস্থিত, তাই মোট বিন্দু অতিক্রম করা হয়েছে 4।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন সাহায্যকারী() সংজ্ঞায়িত করুন। এটি k
- বিন্দুগুলি :=জোড়া (px, py) এবং (qx, qy) সমন্বিত একটি নতুন সেট
- প্রতিটি x, y-এর জন্য k অবস্থান পর্যন্ত পাথে, কর
  - বিন্দুতে জোড়া (x, y) যোগ করুন
- trav:=জোড়া (px, py) ধারণকারী একটি নতুন ডিক
- যখন ট্রাভ খালি না থাকে, কর
  - জোড়া (x, y) :=ট্রাভ থেকে বাঁদিকের আইটেমটি পপ করুন
  - যদি (x, y) একই হয় (qx, qy), তাহলে
    - সত্য ফেরান
  - প্রতিটি kx এর জন্য, ky (x - 1, y), ( x + 1, y), (x, y - 1), (x, y + 1)), do
    - যদি জোড়া (kx, ky) শীর্ষবিন্দুতে থাকে, তাহলে
      - ট্র্যাভের শেষে জোড়া (kx, ky) ঢোকান
      - বিন্দু থেকে জোড়া (kx, ky) মুছুন
  - মিথ্যে ফেরত দিন
ll :=-1
ul :=পথের আকার + 1
যখন ll + 1
k :=ll + ((ul - ll) / 2) এর ফ্লোর মান
যদি সাহায্যকারী(কে) সত্য হয়, তাহলে
- 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]]