力扣3619题:深度优先搜索解决岛屿价值统计
一、问题理解
题目要求我们:
在给定的m×n矩阵grid中识别所有岛屿
岛屿由相邻的正整数单元格组成(上下左右连接)
计算每个岛屿所有单元格值的总和
统计总和能被给定整数k整除的岛屿数量
二、算法选择
解决这类矩阵遍历问题,常见的方法有:
我们选择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; } };
原创内容 转载请注明出处