Tìm số bước di chuyển nhỏ nhất giữa hai ô trong ma trận trong Python

Cho ma trận N x N chứa các giá trị 0, 1, 2, 3. Cần tìm số bước nhỏ nhất từ ô nguồn (giá trị 1) đến ô đích (giá trị 2), chỉ di chuyển qua ô trống (giá trị 3) theo 4 hướng (lên, xuống, trái, phải). Ô giá trị 0 là tường.

Ví dụ ma trận 4x4, kết quả là 5 bước.

Giải thuật (BFS trên đồ thị)

• Chuyển ma trận thành đồ thị: mỗi ô không phải tường là một đỉnh.
• Nối cạnh giữa các ô liền kề hợp lệ (không phải tường).
• Xác định đỉnh nguồn (giá trị 1) và đỉnh đích (giá trị 2).
• Chạy BFS từ nguồn đến đích để tìm đường đi ngắn nhất.

Ví dụ

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj = [[] for _ 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 = [src]
        level[src] = 0
        while queue:
            src = queue.pop(0)
            for v in self.adj[src]:
                if level[v] < 0 or level[v] > level[src] + 1:
                    level[v] = level[src] + 1
                    queue.append(v)
        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
    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))

Đầu vào

[[3,3,1,0], [3,0,3,3], [3,3,0,3], [0,3,2,3]]

Đầu ra

0