Đếm số đảo (Number of Islands) trong Python

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

Ví dụ lưới:

Có ba đảo.

Để giải quyết, chúng ta làm theo các bước sau:

• Có hai phương thức: numIslands() để đếm số đảo và bien_thanh_nuoc(). Phương thức bien_thanh_nuoc() sẽ như sau:

• Nếu số hàng của lưới là 0, trả về 0.

• n = số hàng, m = số cột, ans = 0.

• Với i từ 0 đến n-1:

  • Với j từ 0 đến m-1:
    • Nếu grid[i][j] == "1", ans += 1.
    • Gọi bien_thanh_nuoc(i, j, n, m, grid).

• Phương thức bien_thanh_nuoc nhận chỉ số i, j, số hàng n, số cột m, và lưới grid.

• Nếu i < 0 hoặc j < 0 hoặc i >= n hoặc j >= m, trả về.

• Nếu grid[i][j] == "0", trả về, ngược lại đặt grid[i][j] = "0".

• Gọi đệ quy bien_thanh_nuoc cho 4 hướng: (i+1,j), (i,j+1), (i-1,j), (i,j-1).

Ví dụ

class Solution(object):
    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.bien_thanh_nuoc(i, j, n, m, grid)
        return ans
    
    def bien_thanh_nuoc(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.bien_thanh_nuoc(i+1, j, n, m, grid)
        self.bien_thanh_nuoc(i, j+1, n, m, grid)
        self.bien_thanh_nuoc(i-1, j, n, m, grid)
        self.bien_thanh_nuoc(i, j-1, n, m, grid)

ob1 = Solution()
print(ob1.numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]))

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