力扣3619题：深度优先搜索解决岛屿价值统计

15303105423

一、问题理解

题目要求我们：

• 在给定的m×n矩阵grid中识别所有岛屿
• 岛屿由相邻的正整数单元格组成(上下左右连接)
• 计算每个岛屿所有单元格值的总和
• 统计总和能被给定整数k整除的岛屿数量
  
  

二、算法选择

解决这类矩阵遍历问题，常见的方法有：

• ‌深度优先搜索(DFS)‌：

  
  
  • 递归实现，代码简洁
  • 适合探索所有连通区域
  • 需要处理递归栈空间
    
    

• ‌广度优先搜索(BFS)‌：

  
  
  • 使用队列实现
  • 适合寻找最短路径
  • 需要额外队列空间
    
    

• ‌并查集(Union-Find)‌：

  
  
  • 适合动态连通性问题
  • 实现相对复杂
  • 需要预处理数据结构
    
    

我们选择DFS作为解决方案，因为它最适合这类连通区域统计问题。

三、解法详解

• ‌主函数countIslands‌：

  
  
  • 遍历矩阵每个单元格
  • 发现未访问的陆地(grid[j]>0)时启动DFS
  • 统计满足条件的岛屿数量
    
    

• ‌DFS辅助函数‌：

  
  
  • 递归访问当前单元格的四个邻居
  • 累加岛屿总值
  • 标记已访问单元格(grid[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[j] <= 0) {    return;}

  处理矩阵边界和已访问/非陆地单元格

• ‌访问标记‌：

  grid[j] = -1;

  原地修改矩阵标记已访问，避免额外空间开销

  
  

五、边界情况考虑

• ‌空矩阵‌：直接返回0
• ‌k=1‌：所有岛屿都满足条件
• ‌所有单元格为0‌：没有岛屿
• ‌大矩阵‌：注意递归深度可能导致栈溢出(可改用BFS)
  
  

六、完整代码

1. class Solution {
   
2. private:
   
3.     void dfs(vector<vector<int>>& grid, int i, int j, long long & sum,
   
4.              const vector<pair<int, int>>& directions) {
   
5.         int m = grid.size(), n = grid[0].size();
   
6.         
   
7.         // 边界检查或当前单元格不是陆地
   
8.         if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) {
   
9.             return;
   
10.         }
    
11.         
    
12.         // 累加当前单元格的值并标记为已访问
    
13.         sum += grid[i][j];
    
14.         grid[i][j] = -1;  // 标记为已访问
    
15.         
    
16.         // 向四个方向递归搜索
    
17.         for (const auto& dir : directions) {
    
18.             dfs(grid, i + dir.first, j + dir.second, sum, directions);
    
19.         }
    
20.     }
    
21. public:
    
22.     int countIslands(vector<vector<int>>& grid, int k) {
    
23.         if (grid.empty() || grid[0].empty()) return 0;
    
24.         int m = grid.size(), n = grid[0].size();
    
25.         int count = 0;
    
26.         
    
27.         // 定义方向数组：上、右、下、左
    
28.         vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
29.         
    
30.         for (int i = 0; i < m; ++i) {
    
31.             for (int j = 0; j < n; ++j) {
    
32.                 if (grid[i][j] > 0) {  // 发现新岛屿
    
33.                     long long sum = 0;
    
34.                     dfs(grid, i, j, sum, directions);
    
35.                     if (sum % k == 0) {
    
36.                         ++count;
    
37.                     }
    
38.                 }
    
39.             }
    
40.         }
    
41.         return count;
    
42.     }
    
43. };

复制代码

来源：力扣3619题：深度优先搜索解决岛屿价值统计