Pythonで行列の1つのセルから別のセルに移動するために必要な最小移動数を見つけます

これを解決するには、次の手順に従います-

• ノード：=注文*注文+ 2

• g：=「ノード」数の頂点を持つ空白のグラフ

• k：=1

• 注文する範囲0のiについては、実行してください

  • 注文する範囲0のjについては、次のようにします

    • mat [i、j]が0と同じでない場合、

      • is_ok（i、j + 1、mat）がゼロ以外の場合、

        • kとk+1ノードの間にエッジを作成します

      • is_ok（i、j --1、mat）がゼロ以外の場合、

        • k、k-1ノードの間にエッジを作成します

      • j

        • 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のdestに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