Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm hòn đảo lớn nhất sau khi thay đổi một ô nước thành ô đất 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 1 được bao quanh bởi nước. Chúng ta phải tìm kích thước của hòn đảo lớn nhất. Chúng tôi được phép thay đổi nhiều nhất một ô nước thành ô đất.

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

1 0 1
0 0 0
1 1 0
1 1 1

thì đầu ra sẽ là 7, vì chúng ta có thể chuyển một ô nước lên đất liền để nối hai hòn đảo. Vì vậy, ma trận cuối cùng giống như -

1 0 1
0 0 0
1 1 0
1 1 1

Để 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 tấm lót, C:=số cột của tấm lót

  • mass:=một bản đồ mới

  • id:=555

  • Xác định một hàm tràn ngập (). Điều này sẽ lấy r, c, id

  • nếu r và c nằm trong phạm vi của ma trận và mat [r, c] là 1 thì

    • mat [r, c]:=id

    • khối lượng [id]:=khối lượng [id] + 1

    • cho mỗi cặp (r2, c2) trong [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], thực hiện

      • ngập lụt (r2, c2, id)

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

  • đối với r trong phạm vi từ 0 đến R, thực hiện

    • đối với c trong phạm vi từ 0 đến C, thực hiện

      • nếu mat [r, c] giống 1 thì

        • id:=id + 1

        • khối lượng [id]:=0

        • tràn ngập (r, c, id)

  • ans:=tối đa của (tất cả các giá trị của khối lượng và 1)

  • đối với r trong phạm vi 0 đến R - 1, thực hiện

    • đối với c trong phạm vi 0 đến C - 1, thực hiện

      • nếu mat [r, c] không giống 0 thì

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

      • island_set:=một tập hợp mới

      • cho mỗi cặp (r2, c2) trong [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], thực hiện

        • nếu r2 và c2 nằm trong khoảng của mat và mat [r2, c2] là 1 thì

          • thêm mat [r2, c2] vào island_set

        • ans:=tối đa ans và (1 + tổng của tất cả khối lượng [đảo] cho mỗi đảo inisland_set)

  • trả lại ans

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):
      R, C = len(mat), len(mat[0])
      mass = {}
      id = 555
      def floodfill(r, c, id):
         nonlocal R, C, mat, mass
         if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
            mat[r][c] = id
            mass[id] += 1
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),
               (r, c − 1)]:
               floodfill(r2, c2, id)
                  for r in range(R):
      for c in range(C):
         if mat[r][c] == 1:
            id += 1
            mass[id] = 0
            floodfill(r, c, id)
      ans = max([val for val in mass.values()] + [1])
      for r in range(R):
         for c in range(C):
            if mat[r][c] != 0:
               continue
            island_set = set()
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),(r, c − 1)]:
               if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                  island_set.add(mat[r2][c2])
               ans = max(ans, 1 + sum([mass[island] for island in island_set]))
         return ans
ob = Solution()
matrix = [
   [1, 0, 1],
   [0, 0, 0],
   [1, 1, 0],
   [1, 1, 1]
]
print(ob.solve(matrix))

Đầu vào 

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

Đầu ra 

7