โปรแกรมหาเส้นทางสั้นที่สุดไปยังเป้าหมายในกริดใน Python

ได้กริดมีสัญลักษณ์: '#'=เป้าหมาย, 'O'=ทางเดิน, '*'=ตำแหน่งเริ่มต้น, 'X'=บล็อก หาจำนวนก้าวน้อยที่สุดไปถึง # (4 ทิศทาง) ไม่ถึงได้คืน -1

ตัวอย่าง: กริด 4×4 ผลลัพธ์ 2

วิธีแก้ปัญหา (BFS)

1. หาตำแหน่งเริ่มต้น *
2. BFS แบบระดับ (level-order) ขยาย 4 ทิศทาง
3. เจอ # คืนระดับปัจจุบัน
4. หมดคิวไม่เจอ คืน -1

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

def solve(grid):
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == "*": break
        else: continue
        break
    ans = 0
    queue = [(i, j)]
    grid[i][j] = "X"
    while queue:
        ans += 1
        newq = []
        for i, j in queue:
            for ii, jj in (i-1,j),(i,j-1),(i,j+1),(i+1,j):
                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
                    if grid[ii][jj] == "#": return ans
                    newq.append((ii, jj))
                    grid[ii][jj] = "X"
        queue = newq
    return -1

print(solve([['X','X','O','X'],['X','X','*','X'],['X','#','O','X'],['X','X','X','X']]))

อินพุต

[['X','X','O','X'], ['X','X','*','X'], ['X','#','O','X'], ['X','X','X','X']]

เอาต์พุต

2