पायथन में मैट्रिक्स पर चौड़ाई पहली खोज

किसी दिए गए मैट्रिक्स में, तत्व की स्थिति का विश्लेषण करने के लिए चार ऑब्जेक्ट हैं:बाएँ, दाएँ, नीचे और ऊपर।

Breadth First Search किसी दिए गए 2-D मैट्रिक्स के दो तत्वों के बीच सबसे छोटी दूरी खोजने के अलावा और कुछ नहीं है। इस प्रकार, प्रत्येक सेल में, चार ऑपरेशन होते हैं जिन्हें हम कर सकते हैं जिन्हें चार अंकों में व्यक्त किया जा सकता है जैसे,

'2' वर्णन करता है कि मैट्रिक्स में सेल स्रोत है।
'3' वर्णन करता है कि मैट्रिक्स में सेल गंतव्य है।
'1' वर्णन करता है कि सेल को एक दिशा में आगे ले जाया जा सकता है।
'0' वर्णन करता है कि मैट्रिक्स में सेल को किसी भी दिशा में नहीं ले जाया जा सकता है।

एडोब औचित्य के आधार पर, हम किसी दिए गए मैट्रिक्स पर एक चौड़ाई पहले खोज ऑपरेशन कर सकते हैं।

इस समस्या को हल करने का तरीका

संपूर्ण मैट्रिक्स को पार करने और BFS का उपयोग करके किसी भी सेल के बीच न्यूनतम या सबसे छोटी दूरी खोजने के लिए एल्गोरिथ्म इस प्रकार है:

पहले पंक्ति और कॉलम का इनपुट लें।
दी गई पंक्ति और स्तंभ के साथ एक मैट्रिक्स प्रारंभ करें।
एक पूर्णांक फ़ंक्शन shortestDist(int row, int col, int mat[][col]) इनपुट के रूप में रो, कॉलम और मैट्रिक्स को लेता है और मैट्रिक्स के तत्वों के बीच सबसे छोटी दूरी लौटाता है।
स्रोत के साथ-साथ गंतव्य तत्व का पता लगाने के लिए चर स्रोत और गंतव्य को प्रारंभ करें।
यदि तत्व '3' है, तो इसे गंतव्य के रूप में चिह्नित करें और यदि तत्व '2' है, तो इसे स्रोत तत्व के रूप में चिह्नित करें।
अब दिए गए मैट्रिक्स पर ब्रेडथ फर्स्ट सर्च को लागू करने के लिए क्यू डेटा संरचना को इनिशियलाइज़ करें।
मैट्रिक्स की पंक्ति और स्तंभ को कतार में जोड़े के रूप में सम्मिलित करें। अब सेल में घूमें और पता करें कि यह डेस्टिनेशन सेल है या नहीं। यदि गंतव्य सेल की दूरी वर्तमान सेल से न्यूनतम या कम है, तो दूरी को अपडेट करें।
वर्तमान सेल से सेल की न्यूनतम दूरी ज्ञात करने के लिए फिर से दूसरी दिशा में जाएं।
न्यूनतम दूरी को आउटपुट के रूप में लौटाएं।

उदाहरण

import queue
INF = 10000
class Node:
   def __init__(self, i, j):
      self.row_num = i
      self.col_num = j
def findDistance(row, col, mat):
   source_i = 0
   source_j = 0
   destination_i = 0
   destination_j = 0
   for i in range(0, row):
      for j in range(0, col):
         if mat[i][j] == 2 :
            source_i = i
            source_j = j
         if mat[i][j] == 3 :
            destination_i = i
            destination_j = j
   dist = []
   for i in range(0, row):
      sublist = []
      for j in range(0, col):
         sublist.append(INF)
      dist.append(sublist)
   # initialise queue to start BFS on matrix
   q = queue.Queue()
   source = Node(source_i, source_j)
   q.put(source)
   dist[source_i][source_j] = 0

   # modified BFS by add constraint checks
   while (not q.empty()):
       # extract and remove the node from the front of queue
      temp = q.get()
      x = temp.row_num
      y = temp.col_num

      # If move towards left is allowed or it is the destnation cell
      if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3) :
      # if distance to reach the cell to the left is less than the computed previous path distance, update it
         if dist[x][y] + 1 < dist[x][y - 1] :
            dist[x][y - 1] = dist[x][y] + 1
            next = Node(x, y - 1)
            q.put(next)

      # If move towards right is allowed or it is the destination cell
      if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3) :
         # if distance to reach the cell to the right is less than the computed previous path distance, update it
         if dist[x][y] + 1 < dist[x][y + 1] :
            dist[x][y + 1] = dist[x][y] + 1
            next = Node(x, y + 1)
            q.put(next);

      # If move towards up is allowed or it is the destination cell
      if x - 1 >= 0 and (mat[x - 1][y] == 1 or mat[x-1][y] == 3) :
         # if distance to reach the cell to the up is less than the computed previous path distance, update it
         if dist[x][y] + 1 < dist[x - 1][y] :
            dist[x - 1][y] = dist[x][y] + 1
            next = Node(x - 1, y)
            q.put(next)

      # If move towards down is allowed or it is the destination cell
      if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3) :
         # if distance to reach the cell to the down is less than the computed previous path distance, update it
         if dist[x][y] + 1 < dist[x + 1][y] :
            dist[x + 1][y] = dist[x][y] + 1
            next = Node(x + 1, y)
            q.put(next)
   return dist[destination_i][destination_j]

row = 5
col = 5
mat = [ [1, 0, 0, 2, 1],
      [1, 0, 2, 1, 1],
      [0, 1, 1, 1, 0],
      [3, 2, 0, 0, 1],
      [3, 1, 0, 0, 1] ]

answer = findDistance(row, col, mat);
if answer == INF :
   print("No Path Found")
else:
   print("The Shortest Distance between Source and Destination is:")
   print(answer)

आउटपुट

The Shortest Distance between Source and Destination is:2