力扣3619题：深度优先搜索解决岛屿价值统计
https://dajuwangluo.cn/zb_users/upload/2025/07/202507271753601164253917.jpg一、问题理解题目要求我们：
[*]在给定的m×n矩阵grid中识别所有岛屿
[*]岛屿由相邻的正整数单元格组成(上下左右连接)
[*]计算每个岛屿所有单元格值的总和
[*]统计总和能被给定整数k整除的岛屿数量
二、算法选择解决这类矩阵遍历问题，常见的方法有：
[*]深度优先搜索(DFS)：
[*]递归实现，代码简洁
[*]适合探索所有连通区域
[*]需要处理递归栈空间
[*]广度优先搜索(BFS)：
[*]使用队列实现
[*]适合寻找最短路径
[*]需要额外队列空间
[*]并查集(Union-Find)：
[*]适合动态连通性问题
[*]实现相对复杂
[*]需要预处理数据结构
我们选择DFS作为解决方案，因为它最适合这类连通区域统计问题。三、解法详解
[*]主函数countIslands：
[*]遍历矩阵每个单元格
[*]发现未访问的陆地(grid>0)时启动DFS
[*]统计满足条件的岛屿数量
[*]DFS辅助函数：
[*]递归访问当前单元格的四个邻居
[*]累加岛屿总值
[*]标记已访问单元格(grid=-1)
[*]模运算检查：
[*]每个岛屿搜索完成后检查sum%k==0
[*]满足条件则增加计数器
四、代码细节分析
[*]方向数组：vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};定义了上、右、下、左四个方向的偏移量，简化邻居访问代码
[*]DFS终止条件：if (i < 0 || i >= m || j < 0 || j >= n || grid <= 0) { return;}处理矩阵边界和已访问/非陆地单元格
[*]访问标记：grid = -1;原地修改矩阵标记已访问，避免额外空间开销
五、边界情况考虑
[*]空矩阵：直接返回0
[*]k=1：所有岛屿都满足条件
[*]所有单元格为0：没有岛屿
[*]大矩阵：注意递归深度可能导致栈溢出(可改用BFS)
六、完整代码
class Solution {
private:
void dfs(vector<vector<int>>& grid, int i, int j, long long & sum,
const vector<pair<int, int>>& directions) {
int m = grid.size(), n = grid.size();
// 边界检查或当前单元格不是陆地
if (i < 0 || i >= m || j < 0 || j >= n || grid <= 0) {
return;
}
// 累加当前单元格的值并标记为已访问
sum += grid;
grid = -1;// 标记为已访问
// 向四个方向递归搜索
for (const auto& dir : directions) {
dfs(grid, i + dir.first, j + dir.second, sum, directions);
}
}
public:
int countIslands(vector<vector<int>>& grid, int k) {
if (grid.empty() || grid.empty()) return 0;
int m = grid.size(), n = grid.size();
int count = 0;
// 定义方向数组：上、右、下、左
vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid > 0) {// 发现新岛屿
long long sum = 0;
dfs(grid, i, j, sum, directions);
if (sum % k == 0) {
++count;
}
}
}
}
return count;
}
};来源：力扣3619题：深度优先搜索解决岛屿价值统计
页:
[1]