पायथन में मैट्रिक्स के एक सेल से दूसरे में जाने के लिए आवश्यक चालों की न्यूनतम संख्या ज्ञात करें

मान लीजिए कि हमारे पास एक N X N मैट्रिक्स M है, और यह 1, 0, 2, 3 से भरा है, हमें सोर्स सेल से डेस्टिनेशन सेल में जाने के लिए आवश्यक न्यूनतम संख्या में मूव्स खोजने होंगे। . केवल रिक्त कक्षों के माध्यम से जाने के दौरान, हम ऊपर, नीचे, दाएं और बाएं जा सकते हैं।

• मान 1 वाला सेल स्रोत इंगित करता है।

• 2 मान वाला सेल गंतव्य इंगित करता है।

• 3 मान वाला सेल खाली सेल को दर्शाता है।

• 0 मान वाला सेल खाली दीवार को दर्शाता है।

केवल एक स्रोत और केवल एक गंतव्य कक्ष होगा। स्रोत सेल से गंतव्य तक पहुंचने के लिए एक से अधिक पथ हो सकते हैं। अब, मैट्रिक्स में प्रत्येक चाल को हम '1' मानते हैं।

तो, अगर इनपुट पसंद है

तो आउटपुट 5 होगा,

शुरू से गंतव्य तक हरा पथ सबसे छोटा होता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• नोड्स:=ऑर्डर * ऑर्डर + 2

• g :=एक रिक्त ग्राफ़ जिसमें 'नोड्स' शीर्षों की संख्या होती है

• कश्मीर:=1

• मैं ऑर्डर करने के लिए 0 रेंज में हूं, ऐसा करें

  • ऑर्डर करने के लिए 0 रेंज में j के लिए, करें

    • अगर mat[i, j] 0 के समान नहीं है, तो

      • अगर is_ok (i , j + 1 , mat) गैर-शून्य है, तो

        • k और k + 1 नोड्स g के बीच एक किनारा बनाएं

      • अगर 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

    • अगर मैट [i, j] 2 के समान है, तो

      • नियति :=k

    • कश्मीर:=के + 1

• src से g के गंतव्य तक bfs परफॉर्म करें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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