Pythonでのマトリックスの幅優先探索

特定のマトリックスには、要素の位置を分析するための4つのオブジェクト（左、右、下、上）があります。

幅優先探索は、特定の2次元行列の2つの要素間の最短距離を見つけることに他なりません。したがって、各セルには、実行できる4つの操作があり、次のように4つの数字で表すことができます。

• 「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