একটি গোলকধাঁধা থেকে বেরিয়ে আসার জন্য কম্পাস ব্যবহারের সংখ্যা পাইথনে যথেষ্ট কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন, আমরা একটি খেলা খেলছি যেখানে আমরা একটি গোলকধাঁধায় আটকা পড়েছি। গোলকধাঁধা থেকে আমাদের পথ খুঁজে বের করতে হবে। গোলকধাঁধাটিকে একটি x m ম্যাট্রিক্স হিসাবে উপস্থাপন করা যেতে পারে, যেখানে n হল সারির সংখ্যা এবং m হল কলামের সংখ্যা। ম্যাট্রিক্সের প্রতিটি কক্ষ/উপাদানে 'O', 'D', 'S', বা '-' চিহ্নগুলির যেকোনো একটি থাকে। 'ও' মানে পথ অবরুদ্ধ, 'ডি' হল গোলকধাঁধা থেকে বেরিয়ে আসার পথ, 'এস' হল আমাদের শুরুর অবস্থান, এবং '-' মানে আমরা পথ দিয়ে যেতে পারি। আমরা '-' চিহ্নিত কোষগুলির মধ্যে দিয়ে অবাধে চলাচল করতে পারি। এখন, আমাদের কাছে একটি কম্পাসও রয়েছে যা ব্যবহার করে আমরা গোলকধাঁধা থেকে প্রস্থান পথ ('ডি' সেল) খুঁজে পেতে পারি। যখন আমাদের একটি দিক খুঁজে বের করতে হবে, তখন আমাদের কম্পাস ব্যবহার করতে হবে। কিন্তু, আমরা সর্বাধিক k বার কম্পাস ব্যবহার করতে পারি। একটি ম্যাট্রিক্স হিসাবে গোলকধাঁধা দেওয়া এবং আমরা কম্পাস কতবার ব্যবহার করতে পারি; আমাদের খুঁজে বের করতে হবে যে কম্পাসটি বহুবার ব্যবহার করে আমরা গোলকধাঁধা থেকে বেরিয়ে আসতে পারি কিনা। যদি সম্ভব হয় আমরা সত্য ফেরত দিই, অন্যথায় আমরা মিথ্যা ফেরত দিই।

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

n =4, m =11, k =3; তাহলে আউটপুট হবে True।

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

• একটি ফাংশন সংজ্ঞায়িত করুন path_search()। এটি curr_pos, grid, total_rows, total_cols, k, predecessor নিয়ে যাবে

  • x:=curr_pos

    এর x মান

  • y:=curr_pos

    এর y মান

  • যদি গ্রিড[x, y] "*" এর মত হয়, তাহলে

    • k যদি 0 এর সমান হয়, তাহলে

      • রিটার্ন ট্রু

    • অন্যথায়,

      • রিটার্ন ফলস

    • অন্যথায়,

      • অভিভাবক :=পূর্বসূরী[curr_pos]

      • succ_pos :=succesor_positions (curr_pos, grid, total_rows, total_cols, parent) এর রিটার্ন মান থেকে একটি নতুন তালিকা

      • use_compass :=True যদি succ_pos এর সাইজ> 1

        হয়

      • succ_pos-এ প্রতিটি অবস্থানের জন্য, করুন

        • পূর্বসূরি [অবস্থান] :=curr_pos

        • যদি use_compass অ-শূন্য হয়, তাহলে

          • পাথ_সার্চ(অবস্থান, গ্রিড, মোট_সারি, মোট_কল, কে - 1, পূর্বসূরী)

        • অন্যথায়,

          • পাথ_সার্চ(অবস্থান, গ্রিড, মোট_সারি, মোট_কল, কে, পূর্বসূরী)

• একটি ফাংশন succesor_positions() সংজ্ঞায়িত করুন। এটি curr_pos, grid, total_rows, total_cols, parent

  নেবে

  • x:=curr_pos

    এর x মান

  • y:=curr_pos

    এর y মান

  • succ_pos :=একটি নতুন তালিকা

  • o যদি y> 0, তাহলে

    • বাম :=x, y - 1

    • succ_pos

      এর শেষে বাম দিকে ঢোকান

  • যদি y

    • ডান :=x, y + 1

    • succ_pos

      এর শেষে ডানদিকে সন্নিবেশ করুন

  • যদি x> 0 হয়, তাহলে

    • আপ :=x - 1, y

    • succ_pos

      এর শেষে সন্নিবেশ করুন

  • যদি x <মোট_সারি - 1, তারপর

    • নিচে :=x + 1, y

    • succ_pos

      এর শেষে নিচে প্রবেশ করান

  • যদি succ_pos-এ প্রতিটি অবস্থানের জন্য, গ্রিড[অবস্থান[0], pos[1]] হয়

  • "X" এর মতো নয় এবং pos অভিভাবকের মতো নয়, তারপর −

    ৷

    • শর্ত পূরণ করে succ_pos এ উপাদানগুলি ফেরত দিন

এখন নিম্নলিখিতগুলি সম্পাদন করুন -

• curr_pos :=একটি নতুন খালি জোড়া

• প্রতিটি সূচক i জন্য, গ্রিডে আইটেম সারি, করুন

  • প্রতিটি সূচী j এর জন্য, সারিতে আইটেম উপাদান, করুন

    • যদি উপাদান 'M' এর মত হয়, তাহলে

      • curr_pos :=i, j

        সমন্বিত একটি নতুন জোড়া

• পূর্বসূরী :=একটি নতুন মানচিত্র যেখানে curr_pos :=শুরুতে শূন্য

• path_search(curr_pos, grid, n, m, k, পূর্বসূরী)

সোর্স কোড (পাইথন)

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

def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor):
   x, y = curr_pos
   if grid[x][y] == "D":
      if k == 0:
         print('True')
      else:
         print('False')
   else:
      parent = predecessor[curr_pos]
      succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent))
      use_compass = len(succ_pos) > 1
      for position in succ_pos:
         predecessor[position] = curr_pos
         if use_compass:
            path_search(position, grid, total_rows, total_cols, k - 1, predecessor)
         else:
            path_search(position, grid, total_rows, total_cols, k, predecessor)

def succesor_positions(curr_pos, grid, total_rows, total_cols, pred):
   x, y = curr_pos
   succ_pos = []
   if y > 0:
      left = (x, y - 1)
      succ_pos.append(left)
   if y < total_cols - 1:
      right = (x, y + 1)
      succ_pos.append(right)
   if x > 0:
      up = (x - 1, y)
      succ_pos.append(up)
   if x < total_rows - 1:
      down = (x + 1, y)
      succ_pos.append(down)
   return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos)

def solve(grid, n, m, k):
   curr_pos = ()
   for i, row in enumerate(grid):
      for j, element in enumerate(row):
         if element == 'S':
            curr_pos = (i, j)
   path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None})

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']]

solve(grid, 4, 11, 3)

ইনপুট

grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'],
['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'],
['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'],
['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3

আউটপুট

True