Chương trình tìm đường đi ngắn nhất đến đích trong lưới trong Python

Mô tả bài toán

Cho lưới chứa ký tự: '#' (đích), 'O' (đi được), '*' (vị trí bắt đầu), 'X' (chặn). Tìm số bước tối thiểu từ * đến # (đi 4 hướng), hoặc -1 nếu không đến được.

Ví dụ

Lưới 4x4:

X X O X
X X * X
X # O X
X X X X

Giải thuật (BFS)

1. Tìm vị trí bắt đầu *.
2. BFS từ vị trí đó, đánh dấu đã thăm bằng cách gán 'X'.
3. Mỗi tầng BFS tăng ans lên 1. Nếu gặp '#' trả về ans.
4. Hết hàng đợi -> trả về -1.

Triển khai Python

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']]))

Đầu vào

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

Đầu ra

2