Số lần di chuyển tối thiểu để thoát khỏi ma trận mê cung trong Python

Giả sử chúng ta có một ma trận nhị phân, trong đó 0 đại diện cho một ô trống và 1 là một bức tường. Nếu chúng ta bắt đầu từ góc trên cùng bên trái (0, 0), chúng ta phải tìm số ô tối thiểu để đến góc dưới cùng bên phải (R-1, C-1) Ở đây R là số hàng và C là số trong số các cột. Nếu chúng tôi không thể tìm thấy bất kỳ câu trả lời nào, hãy trả về -1.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 8 vì, chúng ta có thể chọn đường dẫn như -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• R:=số hàng
• C:=số cột
• q:=một danh sách trống, ban đầu chèn (0, 0, 1) nếu ma trận [0, 0] là 0
• ma trận [0, 0]:=1
• đối với mỗi bộ ba (r, c, d) trong q, thực hiện
  • nếu (r, c) giống với (R - 1, C - 1), thì
    • trả về d
  • với mỗi x, y trong [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], thực hiện
    • nếu 0 <=x
    • ma trận [x, y]:=1
    • chèn bộ ba (x, y, d + 1) vào cuối q

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(matrix):
   R, C = len(matrix), len(matrix[0])
   q = [(0, 0, 1)] if not matrix[0][0] else []
   matrix[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 matrix[x][y] == 0:
            matrix[x][y] = 1
            q.append((x, y, d + 1))
   return -1

matrix = [
   [0, 0, 0, 1, 0],
   [0, 0, 1, 1, 0],
   [0, 0, 0, 1, 1],
   [1, 1, 0, 0, 0]
]
print(solve(matrix))

Đầu vào

[
[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 0, 0, 0]
]

Đầu ra

8