Breadth First Search (BFS) trên Ma trận (Matrix) trong Python

Trên ma trận 2D, BFS tìm khoảng cách ngắn nhất giữa 2 ô. 4 hướng: trái, phải, trên, dưới. Mã ô:

• 2: Source (điểm xuất phát)
• 3: Destination (đích)
• 1: Ô có thể di chuyển
• 0: Ô chặn (không đi được)

Thuật toán

1. Nhập row, col, ma trận.
2. Tìm source (2) và destination (3).
3. Khởi tạo mảng distance = INF.
4. Queue BFS: push source, distance[source]=0.
5. Lấy node khỏi queue, kiểm tra 4 hướng: nếu ô hợp lệ (1 hoặc 3) và distance mới < cũ -> cập nhật, push vào queue.
6. Trả về distance[destination].

Ví dụ

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 = source_j = dest_i = dest_j = 0
    for i in range(row):
        for j in range(col):
            if mat[i][j] == 2:
                source_i, source_j = i, j
            if mat[i][j] == 3:
                dest_i, dest_j = i, j
    
    dist = [[INF]*col for _ in range(row)]
    q = queue.Queue()
    q.put(Node(source_i, source_j))
    dist[source_i][source_j] = 0
    
    while not q.empty():
        temp = q.get()
        x, y = temp.row_num, temp.col_num
        
        # Left
        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
                q.put(Node(x, y-1))
        # Right
        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
                q.put(Node(x, y+1))
        # Up
        if x-1 >= 0 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
                q.put(Node(x-1, y))
        # Down
        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
                q.put(Node(x+1, y))
    return dist[dest_i][dest_j]

row, col = 5, 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]
]

ans = findDistance(row, col, mat)
if ans == INF:
    print("No Path Found")
else:
    print("Shortest Distance:", ans)

Kết quả

Shortest Distance: 2