Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1Example:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3问题
给定一个 m x n 的二维二进制网格 grid，它表示一个由 ‘1’（陆地）和 ‘0’（水）组成的地图，返回岛屿的数量。
岛屿被水包围，由水平或垂直连接的陆地组成。你可以假设网格的所有四个边缘都被水包围。
解决方案
深度优先搜索 (DFS) 和广度优先搜索 (BFS)
Approach 1: Depth-First Search (DFS) / 深度优先搜索 (DFS)
This approach uses DFS to explore each island fully. Starting from any ‘1’ that hasn’t been visited, we mark all connected ‘1’s (part of the same island) as visited by setting them to ‘0’. This ensures that we count each island exactly once.
这种方法使用 DFS 来完全探索每个岛屿。从任何未被访问的 ‘1’ 开始，我们将所有连接的 ‘1’（属于同一个岛屿）标记为已访问，方法是将它们设置为 ‘0’。这样可以确保我们每个岛屿只计算一次。
Implementation / 实现
Python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
def dfs(grid, r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == '0':
return
grid[r][c] = '0' # Mark as visited
dfs(grid, r - 1, c)
dfs(grid, r + 1, c)
dfs(grid, r, c - 1)
dfs(grid, r, c + 1)
num_islands = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
num_islands += 1
dfs(grid, r, c)
return num_islandsExplanation / 解释
-
Check for Empty Grid / 检查空网格
if not grid: return 0- English: If the grid is empty, we return 0 since there are no islands.
- Chinese: 如果网格为空，我们返回 0，因为没有岛屿。
-
DFS Function / DFS 函数
def dfs(grid, r, c): if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == '0': return grid[r][c] = '0' # Mark as visited dfs(grid, r - 1, c) dfs(grid, r + 1, c) dfs(grid, r, c - 1) dfs(grid, r, c + 1)- English: The
dfsfunction explores all connected ‘1’s starting from a given cell (r, c), marking them as visited by setting their value to ‘0’. - Chinese:
dfs函数从给定的单元格 (r, c) 开始，探索所有连接的 ‘1’，通过将它们的值设置为 ‘0’ 来标记为已访问。
- English: The
-
Count Islands / 计数岛屿
num_islands = 0 for r in range(len(grid)): for c in range(len(grid[0])): if grid[r][c] == '1': num_islands += 1 dfs(grid, r, c)- English: We iterate through the grid, and for each ‘1’ that we find, we start a DFS to mark the entire island and increment our island count.
- Chinese: 我们遍历网格，对于找到的每个 ‘1’，我们开始 DFS 来标记整个岛屿，并增加岛屿计数。
-
Return the Total Number of Islands / 返回岛屿总数
return num_islands- English: We return the total count of islands found in the grid.
- Chinese: 我们返回在网格中找到的岛屿总数。
Approach 2: Breadth-First Search (BFS) / 广度优先搜索 (BFS)
Alternatively, BFS can be used to explore each island in a similar manner to DFS. Instead of recursion, BFS uses a queue to explore all nodes at the present "depth" level before moving on to nodes at the next depth level.
另外，BFS 也可以用来以类似于 DFS 的方式探索每个岛屿。不同于递归，BFS 使用队列来在移动到下一个深度级别之前，探索当前“深度”级别的所有节点。
BFS Implementation / BFS 实现
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
num_islands = 0
rows, cols = len(grid), len(grid[0])
def bfs(r, c):
queue = deque([(r, c)])
while queue:
row, col = queue.popleft()
if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0':
continue
grid[row][col] = '0'
queue.append((row - 1, col))
queue.append((row + 1, col))
queue.append((row, col - 1))
queue.append((row, col + 1))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
num_islands += 1
bfs(r, c)
return num_islandsExplanation / 解释
-
Initialize BFS and Queue / 初始化 BFS 和队列
from collections import deque- English: We import
dequefromcollectionsto efficiently manage our BFS queue. - Chinese: 我们从
collections导入deque以高效管理 BFS 队列。
- English: We import
-
BFS Function / BFS 函数
def bfs(r, c): queue = deque([(r, c)]) while queue: row, col = queue.popleft() if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == '0': continue grid[row][col] = '0' queue.append((row - 1, col)) queue.append((row + 1, col)) queue.append((row, col - 1)) queue.append((row, col + 1))- English: The
bfsfunction uses a queue to explore all connected ‘1’s starting from a given cell (r, c), marking them as visited by setting their value to ‘0’. - Chinese:
bfs函数使用队列从给定的单元格 (r, c) 开始，探索所有连接的 ‘1’，通过将它们的值设置为 ‘0’ 来标记为已访问。
- English: The
-
Count Islands Using BFS / 使用 BFS 计数岛屿
for r in range(rows): for c in range(cols): if grid[r][c] == '1': num_islands += 1 bfs(r, c)- English: We iterate through the grid, and for each ‘1’ that we find, we start a BFS to mark the entire island and increment our island count.
- Chinese: 我们遍历网格，对于找到的每个 ‘1’，我们开始 BFS 来标记整个岛屿，并增加岛屿计数。
-
Return the Total Number of Islands / 返回岛屿总数
return num_islands- English: We return the total count of islands found in the grid.
- Chinese: 我们返回在网格中找到的岛屿总数。
Recursive Approach / 递归方法
The DFS approach provided can be considered a recursive approach, as it involves recursive function calls to explore each part of an island.
提供的 DFS 方法可以被认为是一种递归方法，因为它涉及递归函数调用来探索岛屿的每个部分。
Complexity Analysis / 复杂度分析
- Time Complexity / 时间复杂度: O(m * n), where m is the number of rows and n is the number of columns in the grid. We potentially visit every cell once.
- Space Complexity / 空间复杂度: O(m * n) in the worst case for the BFS queue or the DFS recursion stack.
Key Concept / 关键概念
- Graph Traversal / 图遍历: Both DFS and BFS are essential techniques for exploring connected components in a grid, which is conceptually similar to graph traversal.
- 图遍历: DFS 和 BFS 都是探索网格中连接组件的基本技术，概念上与图遍历相似。
Summary / 总结
- English: Both DFS and BFS can be used to solve problems involving connected components in grids, such as counting the number of islands.
- Chinese: DFS 和 BFS 都可以用来解决涉及网格中连接组件的问题，例如计算岛屿的数量。
Tips / 提示
- English: Practice both DFS and BFS on grid problems to understand when each approach might be more advantageous.
- Chinese: 在网格问题上练习 DFS 和 BFS，以理解何时每种方法可能更有优势。
Solution Template for Similar Questions / 提示
- English: Consider using DFS or BFS whenever you need to explore all connected components in a grid or graph.
- Chinese: 当你需要探索网格或图中所有连接组件时，考虑使用 DFS 或 BFS。
5 More Similar Questions / 推荐5问题
- LeetCode 130. Surrounded Regions
- LeetCode 417. Pacific Atlantic Water Flow
- LeetCode 695. Max Area of Island
- LeetCode 733. Flood Fill
- LeetCode 694. Number of Distinct Islands
Recommended Resources / 推荐资源
- English: Practice problems that involve grid traversal using DFS or BFS to build a strong understanding of how to navigate and explore grids effectively.
- Chinese: 练习涉及使用 DFS 或 BFS 的网格遍历问题，以建立对如何有效导航和探索网格的深刻理解。
NUMBER OF ISLANDS – Leetcode 200 – Python by NeetCode
Leave a Reply