在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