一文秒杀所有岛屿题目
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 1020. Number of Enclaves | 🟠 |
| 1254. Number of Closed Islands | 🟠 |
| 1905. Count Sub Islands | 🟠 |
| 200. Number of Islands | 🟠 |
| 694. Number of Distinct Islands🔒 | 🟠 |
| 695. Max Area of Island | 🟠 |
Prerequisites
Before reading this article, you should first learn:
The Island series of algorithm problems are classic high-frequency interview questions. While the basic problems are not difficult, there are some interesting extensions, such as finding the number of sub-islands, counting islands with different shapes, etc. This article aims to cover all these problems.
The core focus of the Island series problems is to traverse a 2D array using DFS/BFS algorithms.
This article mainly explains how to use the DFS algorithm to solve the Island series problems quickly. However, the core idea of using the BFS algorithm is exactly the same; it's just a matter of rewriting DFS as BFS.
So, how do you use DFS to search in a 2D matrix? If you consider each position in the 2D matrix as a node, the four positions around it (up, down, left, right) are its adjacent nodes. Thus, the entire matrix can be abstracted into a mesh-like "graph" structure.
According to /essential-technique/algorithm-summary/README.md, you can rewrite the DFS code framework for a 2D matrix based on the traversal framework of a binary tree:
// Binary tree traversal framework
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
}
// Two-dimensional matrix traversal framework
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// out of index bounds
return;
}
if (visited[i][j]) {
// already visited (i, j)
return;
}
// enter the current node (i, j)
visited[i][j] = true;
// enter adjacent nodes (quadtree)
// up
dfs(grid, i - 1, j, visited);
// down
dfs(grid, i + 1, j, visited);
// left
dfs(grid, i, j - 1, visited);
// right
dfs(grid, i, j + 1, visited);
}// Binary tree traversal framework
void traverse(TreeNode* root) {
traverse(root->left);
traverse(root->right);
}
// 2D matrix traversal framework
void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n) {
// out of index bounds
return;
}
if (visited[i][j]) {
// already visited (i, j)
return;
}
// enter the current node (i, j)
visited[i][j] = true;
// enter adjacent nodes (quad tree)
// up
dfs(grid, i - 1, j, visited);
// down
dfs(grid, i + 1, j, visited);
// left
dfs(grid, i, j - 1, visited);
// right
dfs(grid, i, j + 1, visited);
}# Binary tree traversal framework
def traverse(root: TreeNode):
if not root:
return
traverse(root.left)
traverse(root.right)
# 2D matrix traversal framework
def dfs(grid: List[List[int]], i: int, j: int, visited: List[List[bool]]) -> None:
m, n = len(grid), len(grid[0])
if i < 0 or j < 0 or i >= m or j >= n:
# out of index boundary
return
if visited[i][j]:
# already visited (i, j)
return
# enter the current node (i, j)
visited[i][j] = True
# enter the adjacent nodes (quad tree)
# up
dfs(grid, i - 1, j, visited)
# down
dfs(grid, i + 1, j, visited)
# left
dfs(grid, i, j - 1, visited)
# right
dfs(grid, i, j + 1, visited)// Binary tree traversal framework
func traverse(root *TreeNode) {
traverse(root.Left)
traverse(root.Right)
}
// 2D matrix traversal framework
func dfs(grid [][]int, i, j int, visited [][]bool) {
m, n := len(grid), len(grid[0])
if i < 0 || j < 0 || i >= m || j >= n {
// out of index boundary
return
}
if visited[i][j] {
// already visited (i, j)
return
}
// enter the current node (i, j)
visited[i][j] = true
// enter the adjacent nodes (quadtree)
// up
dfs(grid, i - 1, j, visited)
// down
dfs(grid, i + 1, j, visited)
// left
dfs(grid, i, j - 1, visited)
// right
dfs(grid, i, j + 1, visited)
}// Binary tree traversal framework
var traverse = function(root) {
if (!root) {
return;
}
traverse(root.left);
traverse(root.right);
};
// 2D matrix traversal framework
var dfs = function(grid, i, j, visited) {
var m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// out of index boundary
return;
}
if (visited[i][j]) {
// already visited (i, j)
return;
}
// enter current node (i, j)
visited[i][j] = true;
// enter adjacent nodes (quad tree)
// up
dfs(grid, i - 1, j, visited);
// down
dfs(grid, i + 1, j, visited);
// left
dfs(grid, i, j - 1, visited);
// right
dfs(grid, i, j + 1, visited);
};Since a two-dimensional matrix is essentially a "graph," a visited boolean array is needed during traversal to prevent backtracking. If you can understand the code above, solving all island-related problems becomes straightforward.
Additionally, here's a common trick for handling two-dimensional arrays: sometimes you'll see the use of a "direction array" to handle up, down, left, and right traversals, which is similar to the code in the previous article Union-Find Algorithm Explained:
// Direction array, representing up, down, left, right respectively
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// out of index bounds
return;
}
if (visited[i][j]) {
// already visited (i, j)
return;
}
// enter node (i, j)
visited[i][j] = true;
// recursively visit the nodes above, below, left and right
for (int[] d : dirs) {
int next_i = i + d[0];
int next_j = j + d[1];
dfs(grid, next_i, next_j, visited);
}
// leave node (i, j)
}vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void dfs(vector<vector<int>>& grid, int i, int j, vector<vector<bool>>& visited) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || j < 0 || i >= m || j >= n) {
// out of index bounds
return;
}
if (visited[i][j]) {
// already visited (i, j)
return;
}
// enter node (i, j)
visited[i][j] = true;
// recursively traverse the nodes above, below, left, and right
for (auto &d : dirs) {
int next_i = i + d[0];
int next_j = j + d[1];
dfs(grid, next_i, next_j, visited);
}
// leave node (i, j)
}# Direction array, representing up, down, left, and right respectively
dirs = [[-1,0], [1,0], [0,-1], [0,1]]
def dfs(grid: List[List[int]], i: int, j: int, visited: List[List[bool]]) -> None:
m, n = len(grid), len(grid[0])
if i < 0 or j < 0 or i >= m or j >= n:
# out of index boundary
return
if visited[i][j]:
# already visited (i, j)
return
# enter node (i, j)
visited[i][j] = True
# recursively visit the nodes above, below, left, and right
for d in dirs:
next_i = i + d[0]
next_j = j + d[1]
dfs(grid, next_i, next_j, visited)
# leave node (i, j)var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func dfs(grid [][]int, i int, j int, visited [][]bool) {
m, n := len(grid), len(grid[0])
if i < 0 || j < 0 || i >= m || j >= n {
// out of index bounds
return
}
if visited[i][j] {
// already visited (i, j)
return
}
// enter node (i, j)
visited[i][j] = true
// recursively traverse the nodes above, below, left, and right
for _, d := range dirs {
next_i := i + d[0]
next_j := j + d[1]
dfs(grid, next_i, next_j, visited)
}
// leave node (i, j)
}var dirs = [[-1,0], [1,0], [0,-1], [0,1]];
function dfs(grid, i, j, visited) {
let m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// out of index bounds
return;
}
if (visited[i][j]) {
// already visited (i, j)
return;
}
// enter node (i, j)
visited[i][j] = true;
// recursively visit nodes above, below, left, and right
for (let d of dirs) {
let next_i = i + d[0];
let next_j = j + d[1];
dfs(grid, next_i, next_j, visited);
}
// leave node (i, j)
}This approach simply uses a for loop to handle traversal in all directions (up, down, left, right). You can choose the style that suits you best. Below, we will solve the problem using the above framework combined with a visual panel.