Chương trình tìm vùng đất có khoảng cách xa nhất với nước bằng Python

Giả sử chúng ta có một ma trận nhị phân trong đó, 0 đại diện cho nước và 1 đại diện cho đất. Bây giờ chúng ta phải tìm vùng đất có khoảng cách Manhattan xa nhất với mặt nước và cuối cùng là trả lại khoảng cách.

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

thì đầu ra sẽ là 3, vì ô [0,0] có khoảng cách Manhattan từ nước là 3.

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

• nếu A trống, thì
  • trả về 0
• R:=số hàng của ma trận, C:=số cột của ma trận
• khoảng cách:=ma trận có thứ tự R x C và điền bằng 0
• q:=một hàng đợi kết thúc kép với một số cặp (r, c) trong đó r và c là chỉ số hàng và cột của ma trận trong đó ma trận [r, c] bằng 0
• nếu kích thước của q bằng 0 hoặc R * C, thì
  • trả về -1
• trong khi q không trống, hãy thực hiện
  • (r, c):=phần tử bên trái của q, sau đó xóa khỏi q
  • cho mỗi cặp (x, y) trong [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)], thực hiện
    • nếu x và y nằm trong phạm vi của ma trận và A [x, y] là 1 thì
      • A [x, y]:=0
      • khoảng cách [x, y]:=khoảng cách [r, c] + 1
      • chèn (x, y) vào cuối q
• res:=danh sách chứa phần tử tối đa của mỗi hàng
• trả lại tối đa res

Ví dụ (Python)

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

from collections import deque
class Solution:
   def solve(self, A):
      if not A:
         return 0
      R, C = len(A), len(A[0])
      distance = [[0] * C for _ in range(R)]
      q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
      if len(q) in (0, R * C):
         return -1
      while q:
         r, c = q.popleft()
         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]:
               A[x][y] = 0
               distance[x][y] = distance[r][c] + 1
               q.append((x, y))
      return max(max(row) for row in distance)
ob = Solution()
matrix = [
   [1, 1, 1, 1],
   [1, 1, 0, 1],
   [1, 1, 1, 1],
   [0, 0, 1, 1]
]
print(ob.solve(matrix))

Đầu vào

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

Đầu ra

3