Python 中的矩阵广度优先搜索
pythonserver side programmingprogramming更新于 2024/2/18 19:18:00
在给定的矩阵中，有四个对象可以分析元素位置:左、右、下和上。
广度优先搜索就是找到给定二维矩阵的两个元素之间的最短距离。因此，在每个单元格中，我们可以执行四个操作，这些操作可以用四个数字表示，例如，
- "2"表示矩阵中的单元格是源。
- "3"表示矩阵中的单元格是目标。
- "1"表示单元格可以沿某个方向进一步移动。
- "0"描述矩阵中的单元格不能向任何方向移动。
在 Adobe 对齐的基础上，我们可以对给定的矩阵执行广度优先搜索操作。
解决此问题的方法
遍历整个矩阵并使用 BFS 找到任何单元格之间的最小或最短距离的算法如下:
- 首先输入行和列。
- 用给定的行和列初始化矩阵。
- 整数函数 shortestDist(int row, int col, int mat[][col]) 将行、列和矩阵作为输入，并返回矩阵元素之间的最短距离。
- 初始化变量 source 和 destination 以找出源元素和目标元素。
- 如果元素是'3'，然后将其标记为目标，如果元素是'2'，则将其标记为源元素。
- 现在初始化队列数据结构以在给定矩阵上实现广度优先搜索。
- 将矩阵的行和列成对插入队列。现在移动到单元格中并找出它是否是目标单元格。如果目标单元格的距离最小或小于当前单元格，则更新距离。
- 再次移动到另一个方向以找出单元格与当前单元格的最小距离。
- 返回最小距离作为输出。
示例
import queue
INF = 10000
class Node:
def __init__(self, i, j):
self.row_num = i
self.col_num = j
def findDistance(row, col, mat):
source_i = 0
source_j = 0
destination_i = 0
destination_j = 0
for i in range(0, row):
for j in range(0, col):
if mat[i][j] == 2 :
source_i = i
source_j = j
if mat[i][j] == 3 :
destination_i = i
destination_j = j
dist = []
for i in range(0, row):
sublist = []
for j in range(0, col):
sublist.append(INF)
dist.append(sublist)
# 初始化队列以在矩阵上启动 BFS
q =queue.Queue()
source = Node(source_i, source_j)
q.put(source)
dist[source_i][source_j] = 0
# 通过添加约束检查修改 BFS
while (not q.empty()):
# 从队列前面提取并删除节点
temp = q.get()
x = temp.row_num
y = temp.col_num
# 如果允许向左移动或它是目标单元格
if y - 1 >= 0 and (mat[x][y - 1] == 1 or mat[x][y - 1] == 3) :
# 如果到达左侧单元格的距离小于计算出的先前路径距离，则更新它
if dist[x][y] + 1 < dist[x][y - 1] :
dist[x][y - 1] = dist[x][y] + 1
next = Node(x, y - 1)
q.put(next)
# 如果允许向右移动或它是目标单元格
if y + 1 < col and (mat[x][y + 1] == 1 or mat[x][y + 1] == 3) :
# 如果到达右侧单元格的距离小于计算出的上一个路径距离，则更新它
if dist[x][y] + 1 < dist[x][y + 1] :
dist[x][y + 1] = dist[x][y] + 1
next = Node(x, y + 1)
q.put(next);
# 如果允许向上移动或它是目标单元格
如果 x - 1 >= 0 且 (mat[x - 1][y] == 1 或 mat[x-1][y] == 3) :
# 如果到达上方单元格的距离小于计算出的上一个路径距离，则更新它
如果 dist[x][y] + 1 < dist[x - 1][y] :
dist[x - 1][y] = dist[x][y] + 1
next = Node(x - 1, y)
q.put(next)
# 如果允许向下移动或它是目标单元格
if x + 1 < row and (mat[x + 1][y] == 1 or mat[x+1][y] == 3) :
# 如果到达向下单元格的距离小于计算出的上一个路径距离，则更新它
if dist[x][y] + 1 < dist[x + 1][y] :
dist[x + 1][y] = dist[x][y] + 1
next = Node(x + 1, y)
q.put(next)
return dist[destination_i][destination_j]
row = 5
col = 5
mat = [ [1, 0, 0, 2, 1],
[1, 0, 2, 1, 1],
[0, 1, 1, 1, 0],
[3, 2, 0, 0, 1],
[3, 1, 0, 0, 1] ]
answer = findDistance(row, col, mat);
if answer == INF :
print("No Path Found")
else:
print("The Shortest Distance between Source and Destination is:")
print(answer)
输出
The Shortest Distance between Source and Destination is:2
