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

pythonserver side programmingprogramming更新于 2025/9/30 15:40:17

假设我们有一个 N X N 矩阵 M,并且它填充了 1、0、2、3,我们必须找到从源单元格移动到目标单元格所需的最少移动次数。在仅通过空白单元格访问时,我们可以向上、向下、向右和向左访问。

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

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

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

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

只有一个源单元格和一个目标单元格。从源单元格到达目的地可能有多个路径。现在,我们将矩阵中的每个移动视为"1"。

因此,如果输入如下

3310
3033
3303
0323

则输出为 5,

3310
3033
3303
0323

从起点到目的地,绿色路径最短。

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

  • 节点 := order * order + 2

  • g := 带有‘节点’的空白图顶点数

  • k := 1

  • 对于从 0 到 order 范围内的 i,执行

    • 对于从 0 到 order 范围内的 j,执行

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

        • 如果 is_ok (i , j + 1 , mat) 非零,则

          • 在 g 的 k 和 k + 1 个节点之间创建一条边

        • 如果 is_ok (i , j - 1 , mat) 非零,则

          • 在 g 的 k、k - 1 个节点之间创建一条边g

        • 如果 j < order - 1 且 is_ok (i + 1 , j , mat) 非零,则

          • 在 g 的 k、k + order 节点之间创建一条边

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

          • 在 g 的 k、k 阶节点之间创建一条边

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

        • src := k

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

        • dest := k

      • k := k + 1

  • 返回执行从 g 的 src 到 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

相关文章


有用资源