题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

最优解法——遍历+DFS（AC）

深度优先广度优先，当遍历到某个位置grid[i][j]时，判断它是否为1，为1，结果+1，然后则去遍历它的前后左右，为1，也要去遍历它的前后左右
时间复杂度O(n)，空间复杂度O(n)
Beat 87%

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