Tìm số lượng đảo khác nhau trong ma trận 2D trong Python

Cho ma trận nhị phân. Đếm số lượng đảo (island). Đảo là vùng đất (1) bị bao quanh bởi nước (0), kết nối ngang hoặc dọc. Giả sử bốn cạnh ma trận đều là nước.

Ví dụ ma trận 4x5 có 3 đảo.

Thuật toán giải quyết (DFS Flood Fill)

• Hàm numIslands(grid):
  • Nếu rỗng trả về 0.
  • Duyệt mọi ô, nếu grid[i][j] == "1": tăng đếm, gọi make_water(i,j).
• Hàm make_water(i,j,n,m,grid):
  • Nếu ngoài ranh hoặc grid[i][j] == "0": return.
  • Đặt grid[i][j] = "0".
  • Gọi đệ quy 4 hướng: (i+1,j), (i,j+1), (i-1,j), (i,j-1).

Ví dụ minh họa

class Solution:
    def numIslands(self, grid):
        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
        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)

grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
]
sol = Solution()
print(sol.numIslands(grid))  # 3

Đầ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