一、题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
复制代码

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
复制代码

P.S：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’，是字符串，不是数组！

二、思路分析

遍历所有的地方：从遇到的第一个陆地开始，将其标记为访问过的，并对其周围没有访问过的陆地『如此』，最终这一块岛屿就都访问了，然后可以记录的岛屿数加1。
接着寻找到的下一块陆地就是下一个岛屿了领地了，如此往复直到遍历完所有地方。

用DFS和BFS都可以。

时间复杂度分析

所有地方都会访问到，并且只访问一次，所以时间复杂度为O(m*n)。

空间复杂度分析 —— 如何表达『是否访问过』？

思路1：可以用一个二维bool数组，空间复杂度为O(m*n)。
思路2：可以注意到，在遍历过程中，对于越界、遇到水、已访问过的陆地，处理逻辑都是一样的 —— 置之不理。因此如果可以修改grid的的话，可直接将已访问过的陆地设置为”0″。这时候空间复杂度是O(1)。

如何表达『访问周围』？

思路1：直接写。对于上下左右，分别判断是否越界、是否为水陆等，类似的代码写（复制）4份。
思路2：上下左右的坐标相当于当前位置偏差分别是[0,1],[0,-1],[1,0],[-1,0]，可以作为一个数组，再遍历这个数组。在每轮遍历中，当前位置加上偏差得到新的位置，判断是否越界、是否为水陆的逻辑写一次就可以了。

三、AC 代码

Python3 用DFS实现

    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        if rows == 0: return 0
        cols = len(grid[0])
        if cols == 0: return 0

        # 遍历这个岛屿的某一块陆地，最终这个岛屿所有的陆地都变为水
        def dfs(i,j):
            grid[i][j] = '0'
            # 访问四周
            neighbors = [ [0,-1],[0,1],[1,0],[-1,0] ]
            for x,y in neighbors:
                x += i
                y += j
                if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] != '1':
                    continue                
                dfs(x,y)
                
        cnt = 0 # 岛屿数
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    dfs(i,j) 
                    cnt += 1 # 遍历完成后，岛屿数+1
        return cnt
复制代码