3619.总价值可以被 K 整除的岛屿数目：广度优先搜索BFS

【LetMeFly】3619.总价值可以被 K 整除的岛屿数目：广度优先搜索BFS

力扣题目链接：https://leetcode.cn/problems/count-islands-with-total-value-divisible-by-k/

给你一个 m x n 的矩阵 grid 和一个正整数 k。一个 岛屿 是由 正 整数（表示陆地）组成的，并且陆地间 四周 连通（水平或垂直）。

一个岛屿的总价值是该岛屿中所有单元格的值之和。

返回总价值可以被 k 整除 的岛屿数量。

 

示例 1:

输入: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5

输出: 2

解释:

网格中包含四个岛屿。蓝色高亮显示的岛屿的总价值可以被 5 整除，而红色高亮显示的岛屿则不能。

示例 2:

输入: grid = [[3,0,3,0], [0,3,0,3], [3,0,3,0]], k = 3

输出: 6

解释:

网格中包含六个岛屿，每个岛屿的总价值都可以被 3 整除。

 

提示:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• 0 <= grid[i][j] <= 106
• 1 <= k <= 106

解题方法：广度优先搜索

遍历一遍矩阵，遇到非零单位则开始BFS。BFS的作用是：找出所有上下左右相邻非零单元格求和并将单元格置为0，最后返回总和是否能被k整除。

• 时间复杂度$O(mn)$
• 空间复杂度$O(mn)$

注意一个岛屿的总价值可能会超过32位int范围，所以某些编程语言可能需要使用如long long等的64位类型。

AC代码

C++

/*
 * @LastEditTime: 2026-10-26 22:05:14
 */
typedef long long ll;
class Solution {
private:
    int n, m;
    static constexpr int dirs[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    bool inGrid(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }

    bool bfs(vector<vector<int>>& grid, int x, int y, int k) {
        ll cnt = grid[x][y];
        grid[x][y] = 0;
        queue<pair<int, int>> q;
        q.push({x, y});
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto [dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (inGrid(nx, ny) && grid[nx][ny]) {
                    cnt += grid[nx][ny];
                    grid[nx][ny] = 0;
                    q.push({nx, ny});
                }
            }
        }
        return cnt % k == 0;
    }
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    ans += bfs(grid, i, j, k);
                }
            }
        }
        return ans;
    }
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源