给你一个由'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
Solution：
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
row = len(grid)
col = len(grid[0])
num = 0
def dfs(i, j):
if i > row - 1 or j > col - 1 or i < 0 or j < 0 or grid[i][j] == '0':
return
grid[i][j] = '0'
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j - 1)
dfs(i, j + 1)
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
num += 1
dfs(i, j)
return num
解题思路：
像这种向外扩张的题，且不知道深度的，一般都可以选择用dfs（深度优先搜索）递归，Depth-First-Search，那什么是DFS呢，就是一条路有多个岔路，走完一条岔路再走回到交接处从岔路口走第二条。用与BFS相同的图
DFS.png
- 这个图我们从路口1就遇到了岔路口，经过1，接下来我们准备走2或者11，也就是待访问点现在是2、11
- 接下来走2，与2相邻的有3、10，此时待访问点有3、10、11
- 走3，与3相邻的有4，此时待访问点为4、10、11
- 走4，与4相邻的有5、6，此时待访问点为5、6、10、11
- 走5，且没有与5相邻且没访问过的点，此时待访问点为6、10、11
- 5下面没有了回溯到4走6，与6相邻的有7，此时待访问点为7、10、11
- 走7，与7相邻的有8，此时待访问点为8、9、10、11
- 走8，且没有与8相邻且没访问过的点，此时待访问点为9、10、11
- 8下面没有了回溯到7走9，此时待访问点为10、11
- 走与9相邻的10，待访问剩11
- 最后访问11
image.png
回到题目，代码逻辑
- 依次从点出发，我上下左右环视一圈，遇到1说明是岛屿的一部分，那我就顺着这个1发散继续找1，直到遇到0或者边界就跳出
- 每一次我每一个方向走完都会回到上一层递归，所以只要我一次递归完全结束那就是一个完整的岛屿，记录下num
- 为了防止重复寻找，每次遍历到的1，都变为0，这样我下一次就不会把这个地方当成1，减少重复判断（如上图所示）
