【python/M/200】Number of Islands

题目

基本思路

遍历矩阵，每遇到’1’后, 开始向四个方向递归搜索，搜到后变为’0’，因为相邻的属于一个island，然后开始继续找下一个’1’。

实现代码

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