当前位置:首页 > 力扣题解 > 力扣3619题:深度优先搜索解决岛屿价值统计

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

1天前力扣题解56

截图未命名.jpg 力扣3619题:深度优先搜索解决岛屿价值统计 力扣题解 深度优先搜索 矩阵遍历 模运算 深搜 DFS算法 第1张

一、问题理解

题目要求我们:

  1. 在给定的m×n矩阵grid中识别所有岛屿

  2. 岛屿由相邻的正整数单元格组成(上下左右连接)

  3. 计算每个岛屿所有单元格值的总和

  4. 统计总和能被给定整数k整除的岛屿数量

二、算法选择

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

  1. 深度优先搜索(DFS)‌:

  2. 广度优先搜索(BFS)‌:

  3. 并查集(Union-Find)‌:

    • 适合动态连通性问题

    • 实现相对复杂

    • 需要预处理数据结构

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

三、解法详解

  1. 主函数countIslands‌:

    • 遍历矩阵每个单元格

    • 发现未访问的陆地(grid[i][j]>0)时启动DFS

    • 统计满足条件的岛屿数量

  2. DFS辅助函数‌:

    • 递归访问当前单元格的四个邻居

    • 累加岛屿总值

    • 标记已访问单元格(grid[i][j]=-1)

  3. 模运算检查‌:

    • 每个岛屿搜索完成后检查sum%k==0

    • 满足条件则增加计数器

四、代码细节分析

  1. 方向数组‌:

    vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    定义了上、右、下、左四个方向的偏移量,简化邻居访问代码

  2. DFS终止条件‌:

    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) {    return;}

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

  3. 访问标记‌:

    grid[i][j] = -1;

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

五、边界情况考虑

  1. 空矩阵‌:直接返回0

  2. k=1‌:所有岛屿都满足条件

  3. 所有单元格为0‌:没有岛屿

  4. 大矩阵‌:注意递归深度可能导致栈溢出(可改用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;
    }
};



原创内容 转载请注明出处

分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。