Chương trình loại bỏ tất cả các hòn đảo được bao quanh hoàn toàn bởi nước bằng Python

Giả sử chúng ta có một ma trận nhị phân trong đó 1 đại diện cho đất và 0 đại diện cho nước. Và một hòn đảo là một nhóm các số 1 được bao quanh bởi các số 0 (nước) hoặc bởi các cạnh. Chúng tôi phải tìm tất cả các hòn đảo được bao quanh hoàn toàn bởi nước và sửa đổi chúng thành 0. Như chúng ta biết, một hòn đảo hoàn thành được bao quanh bởi nước nếu tất cả các hàng xóm (ngang và dọc không phải là đường chéo) bằng 0 (không có hàng xóm nào là cạnh).

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

thì đầu ra sẽ là

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

• row:=số hàng của A

• col:=số cột của A

• B:=ma trận cỡ A và điền 0

• đã thấy:=một tập hợp mới

• đối với tôi trong phạm vi từ 0 đến hàng, hãy thực hiện

  • đối với j trong phạm vi 0 đến col, do

    • nếu tôi và j không thuộc phạm vi ma trận, thì

      • chuyển sang lần lặp tiếp theo

    • nếu (i, j) được nhìn thấy, thì

      • chuyển sang lần lặp tiếp theo

    • nếu A [i, j] giống 0 thì

      • chuyển sang lần lặp tiếp theo

    • d:=một hàng đợi kết thúc kép với một phần tử (i, j)

    • trong khi d không trống, làm

      • (x, y):=phần tử bên trái của d và xóa khỏi d

      • B [x, y]:=1

      • đối với mỗi hàng xóm (x2, y2) của (x, y), thực hiện

        • nếu (x2, y2) không được nhìn thấy, thì

          • chèn (x2, y2) vào cuối d

          • đánh dấu (x2, y2) như đã thấy

• trả lại B

Ví dụ

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

from collections import deque
class Solution:
   def solve(self, A):
      row = len(A)
      col = len(A[0])
      B = [[0 for _ in range(col)] for _ in range(row)]
      seen = set()
      def nei(i, j):
         if i + 1 < row and A[i + 1][j]:
            yield (i + 1, j)
         if j + 1 < col and A[i][j + 1]:
            yield (i, j + 1)
         if i - 1 >= 0 and A[i - 1][j]:
            yield (i - 1, j)
         if j - 1 >= 0 and A[i][j - 1]:
            yield (i, j - 1)
         for i in range(row):
            for j in range(col):
               if i not in (0, row - 1) and j not in (0, col - 1):
                  continue
               if (i, j) in seen:
                  continue
               if A[i][j] == 0:
                  continue
               d = deque([(i, j)])
               while d:
                  x, y = d.popleft()
                  B[x][y] = 1
                  for x2, y2 in nei(x, y):
                     if (x2, y2) not in seen:
                        d.append((x2, y2))
                        seen.add((x2, y2))
         return B
ob = Solution()
matrix = [
   [1, 0, 0, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [0, 1, 1, 0],
   [0, 0, 0, 1],
]
print(ob.solve(matrix))

Đầu vào

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

Đầu ra

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