Chương trình tìm số lượng các hình dạng đảo riêng biệt từ một ma trận cho trước bằng Python

Giả sử chúng ta có một ma trận nhị phân 2d, chúng ta phải tìm số đảo phân biệt trong ma trận đã cho. Ở đây 1 đại diện cho đất và 0 đại diện cho nước, vì vậy một hòn đảo là một tập hợp các 1 gần nhau và có chu vi được bao quanh bởi nước. Ở đây có hai hòn đảo là duy nhất nếu hình dạng của chúng khác nhau.

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

thì đầu ra sẽ là 4 (các đảo riêng biệt có màu khác nhau).

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

• Định nghĩa một hàm dfs (). Điều này sẽ lấy i, j, k, l

• mat [i, j]:=0

• chèn cặp (i - k, j - l) vào cuối hình

• nếu i + 1

  • dfs (i + 1, j, k, l)

• nếu j + 1

  • dfs (i, j + 1, k, l)

• nếu i - 1> =0 và mat [i - 1, j] là 1 thì

  • dfs (i - 1, j, k, l)

• nếu j - 1> =0 và mat [i, j - 1] là 1 thì

  • dfs (i, j - 1, k, l)

• Từ phương thức chính, hãy làm như sau -

• cnt:=0

• shape:=a new set

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

  • đối với j trong phạm vi 0 đến số cột của thảm, thực hiện

    • nếu mat [i, j] là 1 thì

      • shape:=a new list

      • dfs (i, j, i, j)

      • nếu hình dạng không phải là hình dạng thì

        • cnt:=cnt + 1

      • chèn hình dạng vào hình dạng

• trả lại cnt

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, mat):
      def dfs(i, j, k, l):
         mat[i][j] = 0
         shape.append((i − k, j − l))
      if i + 1 < len(mat) and mat[i + 1][j]:
         dfs(i + 1, j, k, l)
      if j + 1 < len(mat[0]) and mat[i][j + 1]:
         dfs(i, j + 1, k, l)
      if i − 1 >= 0 and mat[i − 1][j]:
         dfs(i − 1, j, k, l)
      if j − 1 >= 0 and mat[i][j − 1]:
         dfs(i, j − 1, k, l)
   cnt = 0
   shapes = set()
      for i in range(len(mat)):
         for j in range(len(mat[0])):
            if mat[i][j]:
               shape = []
               dfs(i, j, i, j)
               shape = tuple(shape)
               if shape not in shapes:
                  cnt += 1
                  shapes.add(shape)
      return cnt
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

Đầu vào

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

Đầu ra

4