> For the complete documentation index, see [llms.txt](https://joey-zhouyicheng.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joey-zhouyicheng.gitbook.io/leetcode/213-200-dao-yu-shu-liang.md).
# 213 - 200 岛屿数量
## 题目
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
> 输入: 11110 11010 11000 00000
>
> 输出: 1
示例 2:
> 输入: 11000 11000 00100 00011
>
> 输出: 3
## 解答
>
flood fill：从一个点开始，深度优先/广度优先遍历，找到所有的的连通区域
### 深度优先
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
marked = [[False for _ in range(n)] for _ in range(m)]
count = 0
def dfs(i, j):
marked[i][j] = True
for direction in directions:
new_i = i + direction[0]
new_j = j + direction[1]
if 0 <= new_i and new_i < m and 0 <= new_j and new_j < n and \
not marked[new_i][new_j] and grid[new_i][new_j] == "1":
dfs(new_i, new_j)
for i in range(m):
for j in range(n):
if not marked[i][j] and grid[i][j] == "1":
count += 1
dfs(i, j)
return count
```
> Runtime: 180 ms, faster than 17.23% of Python3 online submissions for Number of Islands.
>
> Memory Usage: 13.8 MB, less than 67.52% of Python3 online submissions for Number of Islands.
python里面，光`[0]*3`，这是浅拷贝，需要`[0 for _ in range(n)]`才行。。
### 广度优先
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
from collections import deque
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
marked = [[False for _ in range(n)] for _ in range(m)]
count = 0
def bfs(i, j):
queue = deque()
queue.append((i, j))
marked[i][j] = True
while queue:
cur_x, cur_y = queue.popleft()
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
for direction in directions:
new_i = cur_x + direction[0]
new_j = cur_y + direction[1]
if 0 <= new_i and new_i < m and 0 <= new_j and \
new_j < n and not marked[new_i][new_j] and\
grid[new_i][new_j] == "1":
queue.append((new_i, new_j))
marked[new_i][new_j] = True
for i in range(m):
for j in range(n):
if not marked[i][j] and grid[i][j] == "1":
count += 1
bfs(i, j)
return count
```
> Runtime: 196 ms, faster than 11.96% of Python3 online submissions for Number of Islands.
>
> Memory Usage: 13.6 MB, less than 98.29% of Python3 online submissions for Number of Islands.
### dfs之挖人工湖
>
就是把遇到的岛屿全部填成水，就可以少一个markded列表来记录了
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
count = 0
def dfs(i, j):
if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == "0":
return
grid[i][j] = "0"
dfs(i+1, j)
dfs(i, j+1)
dfs(i-1, j)
dfs(i, j-1)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
dfs(i, j)
return count
```
> Runtime: 152 ms, faster than 47.88% of Python3 online submissions for Number of Islands.
>
> Memory Usage: 13.7 MB, less than 82.05% of Python3 online submissions for Number of Islands.
### 光头大佬的版本
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def sink(i, j):
if 0 <= i and i < len(grid) and 0 <= j and j < len(grid[i]) and\
grid[i][j] == "1":
grid[i][j] = "0"
list(map(sink, (i+1, i-1, i, i), (j, j, j+1, j-1)))
return 1
return 0
return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))
```
> Runtime: 416 ms, faster than 5.14% of Python3 online submissions for Number of Islands.
>
> Memory Usage: 14.1 MB, less than 26.50% of Python3 online submissions for Number of Islands.
他也是淹岛
笑死我了哈哈哈哈哈