給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格潮售，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量刘陶。
島嶼總是被水包圍请契，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成咳榜。
此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍爽锥。
示例 ：
輸入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
輸出：3
廣度優(yōu)先搜索和深度優(yōu)先搜索涌韩，是全部遍歷圖的算法，關(guān)鍵在于優(yōu)先的方式不同氯夷，即遍歷的方式不同臣樱。pivot。
深度優(yōu)先搜索腮考，常用保存每一個(gè)搜索的值雇毫，操作上使用
方法。由于棧是
踩蔚，即搜到頭棚放，刪除，往回搜寂纪，再搜到頭席吴。
dfs.gif
# 深度優(yōu)先搜索
class Solution:
def dfs(self, grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
# 搜索該格的上下左右格子
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
# 如果格子是陸地，搜索上下左右格子
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
self.dfs(grid, x, y)
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
# 如果該格是陸地捞蛋，開始深度優(yōu)先搜索
if grid[r][c] == "1":
num_islands += 1
self.dfs(grid, r, c)
return num_islands
