使用 Python 查找从矩阵的一个单元格移动到另一个单元格所需的最小步数

假设我们有一个 N x N 矩阵 M，其中填充了 1、0、2、3。我们必须找到从源单元格移动到目标单元格所需的最小步数。只能经过空白单元格，可以向上、下、右、左移动。

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

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

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

  • 值为 0 的单元格表示障碍物。

只有一个源单元格和一个目标单元格。从源单元格到达目标单元格可能有多条路径。矩阵中的每次移动都算作“1”。

因此，如果输入如下所示：

3310
3033
3303
0323

则输出为 5，

3310
3033
3303
0323

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

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

  • nodes := order * order + 2

  • g := 一个具有“nodes”个顶点的空图

  • k := 1

  • 对于 i 从 0 到 order 的范围：

    • 对于 j 从 0 到 order 的范围：

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

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

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

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

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

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

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

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

          • 在 g 的 k 和 k - order 节点之间创建一条边

      • 如果 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

更新于：2020年8月20日

294 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习
广告