পাইথনে লক্ষ্যে পৌঁছানোর সংক্ষিপ্ততম পথ খুঁজে বের করার প্রোগ্রাম

ধরুন, আমাদের একটি গ্রিড দেওয়া হয়েছে যেখানে কোষে বিভিন্ন চিহ্ন রয়েছে যেমন 'X', 'O', '*' এবং '#' এবং চিহ্নগুলির বিভিন্ন অর্থ রয়েছে৷

• '#' হল সেই লক্ষ্য সেল যা আমরা পেতে চাই।
• 'O' একটি বিনামূল্যের কোষ যার মাধ্যমে আমরা লক্ষ্য কোষে যেতে পারি।
• '*' হল ঘরে আমাদের অবস্থান।
• 'X' একটি অবরুদ্ধ কোষ, যার মাধ্যমে আমরা ভ্রমণ করতে পারি না।

আমাদের গ্রিডে আমাদের বর্তমান অবস্থান থেকে লক্ষ্য কক্ষে পৌঁছানোর জন্য প্রয়োজনীয় চালের সংখ্যা খুঁজে বের করতে হবে। লক্ষ্য পৌঁছানো সম্ভব না হলে, আমরা -1 ফিরে. প্রোগ্রামে ইনপুট হিসাবে গ্রিড দেওয়া হয়।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 2

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

• m :=গ্রিডের সারি গণনা
• n :=গ্রিডের কলাম গণনা
• আমি 0 থেকে m রেঞ্জের জন্য, কর
  0 থেকে n রেঞ্জে j-এর জন্য
  • করুন
    • যদি গ্রিড[i, j] "*" এর মত হয়, তাহলে
      • লুপ থেকে বেরিয়ে আসুন
    • অন্যথায়,
      • পরবর্তী পুনরাবৃত্তির জন্য যান
    • লুপ থেকে বেরিয়ে আসুন
• উত্তর :=0
• সারি :=পূর্ণসংখ্যা জোড়া (i, j) ধারণকারী একটি নতুন তালিকা
• গ্রিড[i, j] :="X"
• যখন সারি খালি না থাকে, কর
  • উত্তর :=উত্তর + ১
  • newq :=একটি নতুন তালিকা
  • প্রতিটি i, j সারির জন্য, do
    • প্রতিটি ii এর জন্য, jj in(i-1, j) ,(i, j-1),(i, j+1),(i+1, j), do
      • যদি 0 <=ii
      • যদি গ্রিড[ii, jj] "#" এর মত হয়, তাহলে
        • উত্তর ফেরত দিন
      • newq-এর শেষে ii, jj ঢোকান
      • গ্রিড[ii, jj] :="X"
• সারি :=newq

উদাহরণ

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

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

ইনপুট

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

আউটপুট

2