> 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.
他也是淹岛
笑死我了哈哈哈哈哈
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://joey-zhouyicheng.gitbook.io/leetcode/213-200-dao-yu-shu-liang.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.