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

Giả sử chúng ta có một lưới 2D đại diện cho một mê cung trong đó 0 là không gian trống và 1 là tường. Chúng ta sẽ bắt đầu ở lưới [0, 0], chúng ta phải tìm số ô vuông tối thiểu để đến góc dưới cùng bên phải của lưới. Nếu chúng tôi không thể tiếp cận, hãy trả về −1.

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

thì đầu ra sẽ là 5

Để 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ủa lưới, C:=số cột của lưới

• q:=[0, 0, 1] khi A [0, 0] là 1 nếu không thì một danh sách mới

• A [0, 0]:=1

• cho mỗi (r, c, d) trong q, thực hiện

  • nếu (r, c) giống với (R - 1, C - 1) thì

    • trở lại d

  • 
    

    • cho mỗi (x, y) trong [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], thực hiện

      • nếu x trong phạm vi 0 đến R và y trong phạm vi 0 đến C và A [x, y] giống 0 thì

        • A [x, y]:=1

        • chèn (x, y, d + 1) vào cuối q

• trả về −1

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

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

Đầu vào

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

Đầu ra

5