Chương trình tìm số ô tối thiểu để đến góc dưới bên phải trong Python

Giả sử chúng ta có một lưới 2D biểu diễn mê cung, trong đó 0 là khoảng trống, và 1 là tường. Chúng ta bắt đầu tại grid[0, 0], phải tìm số ô tối thiểu cần đi để đến góc dưới bên phải của lưới. Nếu không thể đến, trả về -1.

Ví dụ, nếu đầu vào là:

thì đầu ra sẽ là 5

Để giải quyết, chúng ta thực hiện các bước sau:

• R := số hàng của grid, C := số cột của grid
• q := [(0, 0, 1)] nếu A[0][0] là 0, ngược lại danh sách rỗng
• A[0][0] := 1 (đánh dấu đã thăm)
• với mỗi (r, c, d) trong q:
  • nếu (r, c) là (R - 1, C - 1), trả về d
  • với mỗi (x, y) trong [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
    • nếu x trong khoảng 0 đến R và y trong khoảng 0 đến C và A[x][y] bằng 0:
      • A[x][y] := 1
      • thêm (x, y, d + 1) vào cuối q
• trả về -1

Ví dụ

class Solution:
    def solve(self, A):
        R, C = len(A), len(A[0])
        q = [(0, 0, 1)] if not A[0][0] else []
        A[0][0] = 1
        for r, c, d in q:
            if (r, c) == (R - 1, C - 1):
                return d
            for x, y in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
                if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
                    A[x][y] = 1
                    q.append((x, y, d + 1))
        return -1

ob = Solution()
grid = [
    [0, 0, 0],
    [1, 0, 0],
    [1, 0, 0]
]
print(ob.solve(grid))

Input

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

Output

5