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

  • Z时代
  • 2024-01-10
  • 分类：综合

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

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

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

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

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

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

所以，如果输入像

3310
3033
3303
0323

那么输出将为5

3310
3033
3303
0323

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

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

  • 节点：=订单*订单+ 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

    以上是 在Python中找到从矩阵的一个单元移动到另一个单元所需的最少移动次数 的全部内容， 来源链接： utcz.com/z/350198.html

    回到顶部