পাইথনে ম্যাট্রিক্সের এক কক্ষ থেকে অন্য কোষে যাওয়ার জন্য ন্যূনতম সংখ্যক চাল খুঁজে বের করুন

ধরুন আমাদের একটি N X N ম্যাট্রিক্স M আছে, এবং এটি 1, 0, 2, 3 দিয়ে পূর্ণ, আমাদের উৎস সেল থেকে গন্তব্য কক্ষে যাওয়ার জন্য প্রয়োজনীয় নূন্যতম সংখ্যাগুলি খুঁজে বের করতে হবে . শুধুমাত্র ফাঁকা কক্ষের মাধ্যমে পরিদর্শন করার সময়, আমরা উপরে, নীচে, ডান এবং বামে পরিদর্শন করতে পারি।

• 1 মান সহ কক্ষ উৎস নির্দেশ করে৷

  ৷

• মান 2 সহ কক্ষ গন্তব্য নির্দেশ করে৷

  ৷

• 3 মান সহ কক্ষটি ফাঁকা ঘর নির্দেশ করে৷

  ৷

• 0 মান সহ ঘর ফাঁকা প্রাচীর নির্দেশ করে।

শুধুমাত্র একটি উৎস এবং শুধুমাত্র একটি গন্তব্য কোষ থাকবে। সোর্স সেল থেকে গন্তব্যে পৌঁছানোর একাধিক পথ থাকতে পারে। এখন, ম্যাট্রিক্সের প্রতিটি পদক্ষেপকে আমরা '1' হিসাবে বিবেচনা করি।

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

তাহলে আউটপুট হবে 5,

শুরু থেকে গন্তব্য পর্যন্ত সবুজ পথটি সবচেয়ে ছোট৷

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

• নোডস :=অর্ডার * অর্ডার + 2

• g :='নোড' শীর্ষবিন্দুর সংখ্যা সহ একটি ফাঁকা গ্রাফ

• k :=1

• অর্ডার করার জন্য আমি 0 রেঞ্জে আছি, করুন

  • অর্ডার করতে 0 রেঞ্জে j এর জন্য, করুন

    • যদি mat[i, j] 0 এর মত না হয়, তাহলে

      • যদি is_ok (i , j + 1 , mat) অ-শূন্য হয়, তাহলে

        • k এবং k + g এর 1 নোডের মধ্যে একটি প্রান্ত তৈরি করুন

      • যদি is_ok (i , j - 1 , mat) অ-শূন্য হয়, তাহলে

        • k, k - g এর 1 নোডের মধ্যে একটি প্রান্ত তৈরি করুন

      • যদি j <অর্ডার - 1 এবং is_ok (i + 1 , j , mat) অ-শূন্য হয়, তাহলে

        • k, k + g

          এর অর্ডার নোডের মধ্যে একটি প্রান্ত তৈরি করুন

      • যদি i> 0 এবং is_ok (i - 1 , j , mat) অ-শূন্য হয়, তাহলে

        • k, k - অর্ডার নোডের মধ্যে একটি প্রান্ত তৈরি করুন g

    • যদি mat[i, j] 1 এর মত হয়, তাহলে

      • src :=k

    • যদি mat[i, j] 2 এর মত হয়, তাহলে

      • dest :=k

    • k :=k + 1

• src থেকে g এর গন্তব্যে বিএফএস সম্পাদন করুন

উদাহরণ

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

class Graph:
   def __init__(self, nodes):
      self.nodes = nodes
      self.adj = [[] for i in range(nodes)]
   def insert_edge (self, src , dest):
      self.adj[src].append(dest)
      self.adj[dest].append(src)
   def BFS(self, src, dest):
      if (src == dest):
         return 0
      level = [-1] * self.nodes
      queue = []
      level[src] = 0
      queue.append(src)
      while (len(queue) != 0):
         src = queue.pop()
            i = 0
            while i < len(self.adj[src]):
               if (level[self.adj[src][i]] < 0 or level[self.adj[src][i]] > level[src] + 1 ):
level[self.adj[src][i]] = level[src] + 1 queue.append(self.adj[src][i])
               i += 1
      return level[dest]

def is_ok(i, j, mat):
   global order
   if ((i < 0 or i >= order) or (j < 0 or j >= order ) or mat[i][j] == 0):
      return False
   return True
def get_min_math(mat):
   global order
   src , dest = None, None
   nodes = order * order + 2
   g = Graph(nodes)
   k = 1
   for i in range(order):
      for j in range(order):
         if (mat[i][j] != 0):
            if (is_ok (i , j + 1 , mat)):
               g.insert_edge (k , k + 1)
            if (is_ok (i , j - 1 , mat)):
               g.insert_edge (k , k - 1)
            if (j < order - 1 and is_ok (i + 1 , j , mat)):
               g.insert_edge (k , k + order)
            if (i > 0 and is_ok (i - 1 , j , mat)):
               g.insert_edge (k , k - order)
         if(mat[i][j] == 1):
            src = k
         if (mat[i][j] == 2):
            dest = k
         k += 1
   return g.BFS (src, dest)
order = 4
mat = [[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]
print(get_min_math(mat))

ইনপুট

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

আউটপুট

0