力扣3619题：深度优先搜索解决岛屿价值统计
一、问题理解
题目要求我们：
在给定的m×n矩阵grid中识别所有岛屿
岛屿由相邻的正整数单元格组成(上下左右连接)
计算每个岛屿所有单元格值的总和
统计总和能被给定整数k整除的岛屿数量
二、算法选择
解决这类矩阵遍历问题，常见的方法有：
并查集(Union-Find)：
适合动态连通性问题
实现相对复杂
需要预处理数据结构
我们选择DFS作为解决方案，因为它最适合这类连通区域统计问题。
三、解法详解
主函数countIslands：
遍历矩阵每个单元格
发现未访问的陆地(grid[i][j]>0)时启动DFS
统计满足条件的岛屿数量
DFS辅助函数：
递归访问当前单元格的四个邻居
累加岛屿总值
标记已访问单元格(grid[i][j]=-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[i][j] <= 0) { return;}处理矩阵边界和已访问/非陆地单元格
访问标记：
grid[i][j] = -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[0].size();
// 边界检查或当前单元格不是陆地
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) {
return;
}
// 累加当前单元格的值并标记为已访问
sum += grid[i][j];
grid[i][j] = -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[0].empty()) return 0;
int m = grid.size(), n = grid[0].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[i][j] > 0) { // 发现新岛屿
long long sum = 0;
dfs(grid, i, j, sum, directions);
if (sum % k == 0) {
++count;
}
}
}
}
return count;
}
};原创内容 转载请注明出处
