原创回溯算法约 4443 字大约 15 分钟
Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
岛屿系列算法问题是经典的面试高频题,虽然基本的问题并不难,但是这类问题有一些有意思的扩展,比如求子岛屿数量,求形状不同的岛屿数量等等,本文就来把这些问题一网打尽。
岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。
本文主要来讲解如何用 DFS 算法来秒杀岛屿系列题目,不过用 BFS 算法的核心思路是完全一样的,无非就是把 DFS 改写成 BFS 而已。
那么如何在二维矩阵中使用 DFS 搜索呢?如果你把二维矩阵中的每一个位置看做一个节点,这个节点的上下左右四个位置就是相邻节点,那么整个矩阵就可以抽象成一幅网状的「图」结构。
根据 学习数据结构和算法的框架思维,完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架:
java 🟢
// 二叉树遍历框架
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
}
// 二维矩阵遍历框架
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) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
dfs(grid, i - 1, j, visited); // 上
dfs(grid, i + 1, j, visited); // 下
dfs(grid, i, j - 1, visited); // 左
dfs(grid, i, j + 1, visited); // 右
}
cpp 🤖
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
void traverse(TreeNode* root) {
traverse(root->left);
traverse(root->right);
}
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) {
return;
}
if (visited[i][j]) {
return;
}
visited[i][j] = true;
dfs(grid, i - 1, j, visited); // 上
dfs(grid, i + 1, j, visited); // 下
dfs(grid, i, j - 1, visited); // 左
dfs(grid, i, j + 1, visited); // 右
}
python 🤖
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# 二叉树遍历框架
def traverse(root: TreeNode):
if not root:
return
traverse(root.left)
traverse(root.right)
# 二维矩阵遍历框架
def dfs(grid: List[List[int]], i: int, j: int, visited: List[List[bool]]):
m, n = len(grid), len(grid[0])
if i < 0 or j < 0 or i >= m or j >= n:
# 超出索引边界
return
if visited[i][j]:
# 已遍历过 (i, j)
return
# 进入节点 (i, j)
visited[i][j] = True
dfs(grid, i - 1, j, visited) # 上
dfs(grid, i + 1, j, visited) # 下
dfs(grid, i, j - 1, visited) # 左
dfs(grid, i, j + 1, visited) # 右
go 🤖
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 二叉树遍历框架
func traverse(root *TreeNode) {
traverse(root.Left)
traverse(root.Right)
}
// 二维矩阵遍历框架
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 {
// 超出索引边界
return
}
if visited[i][j] {
// 已遍历过 (i, j)
return
}
// 进入节点 (i, j)
visited[i][j] = true
dfs(grid, i-1, j, visited) // 上
dfs(grid, i+1, j, visited) // 下
dfs(grid, i, j-1, visited) // 左
dfs(grid, i, j+1, visited) // 右
}
javascript 🤖
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var traverse = function(root) {
traverse(root.left);
traverse(root.right);
};
var dfs = function(grid, i, j, visited) {
var m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
dfs(grid, i - 1, j, visited); // 上
dfs(grid, i + 1, j, visited); // 下
dfs(grid, i, j - 1, visited); // 左
dfs(grid, i, j + 1, visited); // 右
};
因为二维矩阵本质上是一幅「图」,所以遍历的过程中需要一个 visited
布尔数组防止走回头路,如果你能理解上面这段代码,那么搞定所有岛屿系列题目都很简单。
这里额外说一个处理二维数组的常用小技巧,你有时会看到使用「方向数组」来处理上下左右的遍历,和前文 union-find 算法详解 的代码很类似:
java 🟢
// 方向数组,分别代表上、下、左、右
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) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
// 递归遍历上下左右的节点
for (int[] d : dirs) {
int next_i = i + d[0];
int next_j = j + d[1];
dfs(grid, next_i, next_j, visited);
}
// 离开节点 (i, j)
}
cpp 🤖
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
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) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
// 递归遍历上下左右的节点
for (auto &d : dirs) {
int next_i = i + d[0];
int next_j = j + d[1];
dfs(grid, next_i, next_j, visited);
}
// 离开节点 (i, j)
}
python 🤖
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# 方向数组,分别代表上、下、左、右
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:
# 超出索引边界
return
if visited[i][j]:
# 已遍历过 (i, j)
return
# 进入节点 (i, j)
visited[i][j] = True
# 递归遍历上下左右的节点
for d in dirs:
next_i = i + d[0]
next_j = j + d[1]
dfs(grid, next_i, next_j, visited)
# 离开节点 (i, j)
go 🤖
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func dfs(grid [][]int, i int, j int, visited [][]bool) {
var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var dfsCore func(i, j int)
dfsCore = func(i int, j int) {
m, n := len(grid), len(grid[0])
if i < 0 || j < 0 || i >= m || j >= n {
// 超出索引边界
return
}
if visited[i][j] {
// 已遍历过 (i, j)
return
}
// 进入节点 (i, j)
visited[i][j] = true
// 递归遍历上下左右的节点
for _, d := range dirs {
next_i := i + d[0]
next_j := j + d[1]
dfsCore(next_i, next_j)
}
// 离开节点 (i, j)
}
dfsCore(i, j)
}
javascript 🤖
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var dirs = [[-1,0], [1,0], [0,-1], [0,1]];
function dfs(grid, i, j, visited) {
var m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
// 递归遍历上下左右的节点
for (var d of dirs) {
var next_i = i + d[0];
var next_j = j + d[1];
dfs(grid, next_i, next_j, visited);
}
// 离开节点 (i, j)
}
这种写法无非就是用 for 循环处理上下左右的遍历罢了,你可以按照个人喜好选择写法。下面就按照上述框架结合可视化面板来解题。