在 Python 中查找从矩阵的一个单元格移动到另一个单元格所需的最少移动次数
假设我们有一个 N X N 矩阵 M,并且它填充了 1、0、2、3,我们必须找到从源单元格移动到目标单元格所需的最少移动次数。在仅通过空白单元格访问时,我们可以向上、向下、向右和向左访问。
值为 1 的单元格表示源。
值为 2 的单元格表示目的地。
值为 3 的单元格表示空白单元格。
值为 0 的单元格表示空白墙。
只有一个源单元格和一个目标单元格。从源单元格到达目的地可能有多个路径。现在,我们将矩阵中的每个移动视为"1"。
因此,如果输入如下
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
则输出为 5,
| 3 | 3 | 1 | 0 |
| 3 | 0 | 3 | 3 |
| 3 | 3 | 0 | 3 |
| 0 | 3 | 2 | 3 |
从起点到目的地,绿色路径最短。
为了解决这个问题,我们将遵循以下步骤 −
节点 := 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

