Tìm số đảo riêng biệt trong ma trận 2D bằng Python

Giả sử chúng ta có một ma trận nhị phân. Chúng tôi phải đếm số lượng các hòn đảo trong đó. Đảo là nơi được bao quanh bởi nước và được hình thành bằng cách kết nối các vùng đất liền kề theo chiều ngang hoặc chiều dọc. Chúng ta có thể giả định rằng tất cả bốn cạnh của lưới đều được bao quanh bởi nước.

Giả sử lưới giống như -

Có ba hòn đảo.

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

• Sẽ có hai phương thức, một phương thức sẽ được sử dụng để đếm số hòn đảo được gọi là numIslands () và makeWater (). MakeWater () sẽ giống như -

• nếu số hàng trong lưới là 0, thì trả về 0

• n =số hàng và m:=số cột và ans:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • cho j trong phạm vi từ 0 đến m

    • nếu lưới [i, j] =1, thì ans:=ans + 1

    • makeWater (i, j, n, m, lưới)

• makeWater () sẽ lấy các chỉ số i, j, hàng và col đếm n và m, và lưới

• nếu tôi <0 hoặc j <0 hoặc i> =n hoặc j> =m, thì trả về từ phương thức này

• nếu lưới [i, j] =0, thì trả về, ngược lại hãy tạo lưới [i, j]:=0

• gọi makeWater (i + 1, j, n, m, lưới)

• gọi makeWater (i, j + 1, n, m, lưới)

Ví dụ

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

class Solution(object):
   def numIslands(self, grid):
      """
      :type grid: List[List[str]]
      :rtype: int
      """
      if len(grid) == 0:
         return 0
      n= len(grid)
      m = len(grid[0])
      ans = 0
      for i in range(n):
         for j in range(m):
            if grid[i][j] == "1":
               ans+=1
            self.make_water(i,j,n,m,grid)
         return ans
   def make_water(self,i,j,n,m,grid):
      if i<0 or j<0 or i>=n or j>=m:
         return
      if grid[i][j] == "0":
         return
      else:
         grid[i][j]="0"
      self.make_water(i+1,j,n,m,grid)
      self.make_water(i,j+1,n,m,grid)
      self.make_water(i-1,j,n,m,grid)
      self.make_water(i,j-1,n,m,grid)

Đầu vào

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

Đầu ra

3