หาจำนวนการเคลื่อนที่น้อยที่สุดในเมทริกซ์จากจุดเริ่มต้นไปจุดหมายใน Python

สมมติว่าเรามีเมทริกซ์ N x N ที่มีค่า 0, 1, 2, 3 โดย:

• 1 = จุดเริ่มต้น (Source)
• 2 = จุดหมาย (Destination)
• 3 = ช่องว่าง (Blank cell)
• 0 = กำแพง (Wall)

สามารถเคลื่อนที่ได้ 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา) ผ่านช่องว่างเท่านั้น หาจำนวนการเคลื่อนที่น้อยที่สุดจากจุดเริ่มต้นไปจุดหมาย

เช่น เมทริกซ์ 4x4 ตัวอย่าง ผลลัพธ์คือ 5

ขั้นตอนการแก้ปัญหา (BFS บนกราฟ)

1. สร้างกราฟโดยแปลงแต่ละเซลล์ที่ไม่ใช่กำแพงเป็นโหนด
2. เชื่อมโหนดที่อยู่ติดกันและไม่ใช่กำแพง
3. หาตำแหน่ง source และ destination
4. รัน BFS จาก source ไป destination คืนค่าระยะทาง

ตัวอย่างโค้ด Python

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, 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):
    order = len(mat)
    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, order):
                    g.insert_edge(k, k + 1)
                if is_ok(i, j - 1, mat, order):
                    g.insert_edge(k, k - 1)
                if j < order - 1 and is_ok(i + 1, j, mat, order):
                    g.insert_edge(k, k + order)
                if i > 0 and is_ok(i - 1, j, mat, order):
                    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]]

เอาต์พุต

5