3619. 总价值可以被 K 整除的岛屿数目

来源第 161 场双周赛 Q2难度中等分数1461

题目描述

给你一个 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 <= 10⁵
0 <= grid[i][j] <= 10⁶
1 <= k < = 10⁶

解法

方法一：DFS

思考

岛屿是四连通的正值格子。需要的是每座岛的价值和能否被 \(k\) 整除，而不是形状。深度优先搜索在访问时累加并清零，既求面积又避免重复访问。

遍历网格，对每个仍为正的格子启动 \(\textit{dfs}\)，若返回值模 \(k\) 为 \(0\) 则计数加一。方向数组 \((-1,0,1,0,-1)\) 生成四邻接。

每个格子进出一次，时间与网格规模成正比。

我们定义一个函数 \(\textit{dfs}(i, j)\)，它从位置 \((i, j)\) 开始进行 DFS 遍历，并且返回该岛屿的总价值。我们将当前位置的值加入总价值，然后将该位置标记为已访问（例如，将其值设为 0）。接着，我们递归地访问四个方向（上、下、左、右）的相邻位置，如果相邻位置的值大于 0，则继续进行 DFS，并将其值加入总价值。最后，我们返回总价值。

在主函数中，我们遍历整个网格，对于每个未访问的位置 \((i, j)\)，如果其值大于 0，则调用 \(\textit{dfs}(i, j)\) 来计算该岛屿的总价值。如果总价值可以被 \(k\) 整除，则将答案加一。

时间复杂度 \(O(m \times n)\)，空间复杂度 \(O(m \times n)\)。其中 \(m\) 和 \(n\) 分别是网格的行数和列数。

Python3JavaC++GoTypeScript

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        def dfs(i: int, j: int) -> int:
            s = grid[i][j]
            grid[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    s += dfs(x, y)
            return s

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] and dfs(i, j) % k == 0:
                    ans += 1
        return ans

class Solution {
    private int m;
    private int n;
    private int[][] grid;
    private final int[] dirs = {-1, 0, 1, 0, -1};

    public int countIslands(int[][] grid, int k) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0 && dfs(i, j) % k == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private long dfs(int i, int j) {
        long s = grid[i][j];
        grid[i][j] = 0;
        for (int d = 0; d < 4; ++d) {
            int x = i + dirs[d], y = j + dirs[d + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                s += dfs(x, y);
            }
        }
        return s;
    }
}

class Solution {
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dirs = {-1, 0, 1, 0, -1};

        auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
            long long s = grid[i][j];
            grid[i][j] = 0;
            for (int d = 0; d < 4; ++d) {
                int x = i + dirs[d], y = j + dirs[d + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                    s += dfs(x, y);
                }
            }
            return s;
        };

        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] && dfs(i, j) % k == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

func countIslands(grid [][]int, k int) (ans int) {
    m, n := len(grid), len(grid[0])
    dirs := []int{-1, 0, 1, 0, -1}
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        s := grid[i][j]
        grid[i][j] = 0
        for d := 0; d < 4; d++ {
            x, y := i+dirs[d], j+dirs[d+1]
            if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0 {
                s += dfs(x, y)
            }
        }
        return s
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > 0 && dfs(i, j)%k == 0 {
                ans++
            }
        }
    }
    return
}

function countIslands(grid: number[][], k: number): number {
    const m = grid.length,
        n = grid[0].length;
    const dirs = [-1, 0, 1, 0, -1];
    const dfs = (i: number, j: number): number => {
        let s = grid[i][j];
        grid[i][j] = 0;
        for (let d = 0; d < 4; d++) {
            const x = i + dirs[d],
                y = j + dirs[d + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                s += dfs(x, y);
            }
        }
        return s;
    };

    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] > 0 && dfs(i, j) % k === 0) {
                ans++;
            }
        }
    }

    return ans;
}

方法二：显式栈

思考

岛屿是四连通的正值格子，答案只取决于每座岛的价值和能否被 \(k\) 整除。对每个仍为正的格子做一次递归搜索，在进入格子时累加并清零，就能求出这座岛的和，同时避免把同一格子算进两座岛。

网格规模达到 \(10^5\)。一条蛇形岛屿会让递归深度跟着格子数一起增长，调用栈在求和结束前就会溢出。清零只是访问标记，邻格是否属于同一座岛仍然只看它是否仍为正。

待扩展的坐标可以放进显式栈。格子的值在入栈前加进总和并立刻清零，弹出后再把四个仍为正的邻居入栈，这样总和与递归版本一致，而栈的深度由我们自己控制。单格不超过 \(10^6\)、格子数不超过 \(10^5\)，一座岛的和可以到 \(10^{11}\)，因此总和用 64 位整数保存。

扫描整张网格，每遇到仍为正的格子就做一次这样的遍历，返回的和模 \(k\) 为 \(0\) 时答案加一。每个格子至多入栈一次。

我们用显式栈遍历每一座岛屿。从仍为正的格子 \((i, j)\) 出发，先把它的值记入总和 \(s\)，再将该格清零并压入栈。每次弹出一个格子，检查上、下、左、右四个相邻位置：若邻居仍为正，则把它的值累加到 \(s\)，清零后压栈。栈空时， \(s\) 就是这座岛的总价值。清零发生在入栈之前，同一格子不会被重复累加。

主函数扫描整个网格。遇到仍为正的格子就执行上述遍历，若 \(s \bmod k = 0\) 则答案加一。 \(s\) 使用 64 位整数，避免 \(10^5\) 个不超过 \(10^6\) 的格子相加时溢出。