在Python中找到从矩阵的一个单元移动到另一个单元所需的最少移动次数

假设我们有一个NXN矩阵M，并用1，0，2，3填充，我们必须找到从源像元移动到目标像元所需的最小移动数。仅通过空白单元格访问时，我们可以向上，向下，向右和向左访问。

• 值为1的单元格表示“源”。

• 值为2的单元格表示目标。

• 值为3的单元格表示空白单元格。

• 值为0的单元格表示“空白墙”。

将只有一个源，只有一个目标单元。从源单元到达目的地的路径可能不止一条。现在，矩阵中的每一步我们都认为是“ 1”。

所以，如果输入像

那么输出将为5

从起点到终点，绿色路径最短。

为了解决这个问题，我们将遵循以下步骤-

• 节点：=订单*订单+ 2

• g：=顶点数为'nodes'的空白图形

• k：= 1

• 对于范围为0的i，执行

• 如果mat [i，j]不等于0，则

• 如果mat [i，j]与1相同，则

• 如果mat [i，j]与2相同，则

• k：= k + 1

• 在k，k-g的阶数节点之间创建边

• 在k，k + g的阶节点之间创建边

• 在k，k-g的1节点之间创建边

• 在k和k + 1g节点之间创建边

• 如果is_ok（i，j + 1，mat）不为零，则

• 如果is_ok(i,j-1,mat)不为零，则

• 如果j <order-1并且is_ok（i + 1，j，mat）为非零，则

• 如果i> 0并且is_ok(i-1,j,mat)为非零，则

• src：= k

• 目标：= k

• 对于范围为0的j，执行

• 将执行bfs从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