পাইথনে একটি বোমা জড়িত না করে একটি আয়তক্ষেত্রাকার এলাকায় একটি অবিচ্ছিন্ন পথ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে ম্যাট দেওয়া হয়েছে যেখানে উপাদানগুলি এই ফর্মের [p, q, r] যেখানে p, q হল জ্যামিতিক স্থানাঙ্ক এবং r হল একটি ব্যাসার্ধের মান। অ্যারের আইটেম হল একটি প্রদত্ত প্রস্থ w এর আয়তক্ষেত্রাকার এলাকায় বোমার অবস্থান। আয়তক্ষেত্রটি অসীমভাবে দীর্ঘ এবং x স্থানাঙ্ক x =0 থেকে x =w দ্বারা আবদ্ধ। বোমার অবস্থানে r মান একটি বোমার সুরক্ষা ব্যাসার্ধকে নির্দেশ করে, যার অর্থ বোমার ব্যাসার্ধের চেয়ে কম কিছু এটিকে জড়িত করবে। সুতরাং, আমাদের যা করতে হবে তা হল একটি অবিচ্ছিন্ন পথ আঁকতে যা প্রতিটি বোমার নীচে থেকে শুরু হয় এবং প্রতিটি বোমার উপরে শেষ হয় তাদের কোনও একটিকে জড়িত না করে। আমরা সত্য প্রিন্ট করব যদি আমরা এই লাইনটি আঁকতে পারি, অন্যথায়, আমরা মিথ্যা প্রিন্ট করব।

সুতরাং, যদি ইনপুট ম্যাট =

এর মত হয়

0	1	2
3	2	1
2	1	1

, w =4; তাহলে আউটপুট False হবে।

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

একটি ফাংশন insec() সংজ্ঞায়িত করুন। এটি p, q
- x1 :=p[1], x2 :=p[2]
- y2 :=q[1], y4 :=q[2]
- r1 :=p[3], r2 :=q[3]
- d :=(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
- ডিসে :=(r1 + r2) *(r1 + r2)
- রিটার্ন True যদি d <=dec, অন্যথায় False দিন
x স্থানাঙ্ক মানের উপর ভিত্তি করে ম্যাট্রিক্স সাজান
temp :=একটি নতুন তালিকা
যদি mat[0][0] - mat[0][2]> 0, তারপর
- সত্য ফেরান
প্রতিটি p, q, r-এর জন্য মাদুরে, do
- min_wid :=p - r
- max_wid :=p + r
- যদি তাপমাত্রার আকার 0 এর মতো হয়, তাহলে
  - টেম্পের শেষে (p + r, p, q, r, p - r, p + r) ধারণকারী তালিকা যোগ করুন
- অন্যথায়,
  - mx :=সর্বাধিক (অস্থায়ী অবস্থান যেখানে তালিকা [p - r, -p, q, r, 0, 0] সাজানো ক্রম বজায় রেখে সন্নিবেশ করা যেতে পারে - 1) , 0
  - in_list :=উপাদান সমন্বিত একটি নতুন তালিকা (p + r, p, q, r, p - r, p + r)
  - আমি পরিসীমা mx থেকে তাপমাত্রার আকারের জন্য, কর
    - যদি insec(temp[i], in_list) সত্য হয়, তাহলে
      - max_wid =সর্বাধিক (max_wid, temp[i, -1])
    - min_wid =সর্বনিম্ন (min_wid, temp[i, -2])
  - in_list এর দ্বিতীয় শেষ উপাদান :=min_wid
  - in_list এর শেষ_এলিমেন্ট :=max_wid
  - অস্থায়ীভাবে সাজানো ক্রম বজায় রাখার জন্য in_list সন্নিবেশ করুন
- যদি min_wid <=0 এবং max_wid>=w হয়, তাহলে
  - মিথ্যে ফেরত দিন
সত্য ফেরান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from bisect import bisect_left, insort
def solve(mat, w):
   mat.sort(key=lambda i: i[0] - i[2])
   temp = []
   if mat[0][0] - mat[0][2] > 0:
      return True
   for p, q, r in mat:
      min_wid, max_wid = p - r, p + r
      if len(temp) == 0:
         temp.append([p + r, p, q, r, p - r, p + r])
      else:
         mx = max(bisect_left(temp, [p - r, -p, q, r, 0, 0]) - 1, 0)

         in_list = [p + r, p, q, r, p - r, p + r]
         for i in range(mx, len(temp)):
             if insec(temp[i], in_list):
               max_wid = max(max_wid, temp[i][-1])
               min_wid = min(min_wid, temp[i][-2])
         in_list[-2] = min_wid
         in_list[-1] = max_wid
         insort(temp, in_list)
      if min_wid <= 0 and max_wid >= w:
         return False
   return True

def insec(p, q):
   x1, y1, x2, y2 = p[1], p[2], q[1], q[2]
   r1, r2 = p[3], q[3]
   d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
   dec = (r1 + r2) * (r1 + r2)
   return d <= dec

print(solve([[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4))

ইনপুট

[[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4

আউটপুট

False