总价值可以被 K 整除的岛屿数目【力扣LeetCode 每日一题】

发布时间：2026/10/28 10:21:03

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

网页链接

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

输出：

解释：

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

示例 2

输入：

grid = [[3,0,3,0],[0,3,0,3],[3,0,3,0]], k = 3

输出：

解释：

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

数据范围

m = = grid.length m == \text{grid.length}m==grid.length
n = = grid [ i ] .length n == \text{grid}[i]\text{.length}n==grid[i].length
1 ≤ m , n ≤ 1000 1 \le m, n \le 10001≤m,n≤1000
1 ≤ m × n ≤ 10 5 1 \le m \times n \le 10^51≤m×n≤105
0 ≤ grid [ i ] [ j ] ≤ 10 5 0 \le \text{grid}[i][j] \le 10^50≤grid[i][j]≤105
1 ≤ k ≤ 10 6 1 \le k \le 10^61≤k≤106

解题思路

本题是网格连通块搜索 + 连通块权值求和问题。矩阵中非零正整数表示陆地，0表示水。上下左右四个方向连通的陆地组成一个岛屿，岛屿的总价值是其所有单元格数值之和。需要统计总价值能被k kk整除的岛屿数量。

1. 问题等价转化

把每个由非零整数组成的四连通块看作一个岛屿。对每个岛屿，计算：
S = ∑ 该岛屿所有单元格 g r i d [ i ] [ j ] S = \sum_{\text{该岛屿所有单元格}} grid[i][j]S=该岛屿所有单元格∑grid[i][j]
若满足：
S m o d k = 0 S \bmod k = 0Smodk=0
则该岛屿计入答案。

因此只需遍历所有陆地，找到每个完整连通块并求其总和即可。

2. 遍历与发现新岛屿

从左上到右下扫描矩阵：

若grid[i][j] == 0，说明是水或已访问过的陆地，跳过；
若grid[i][j] != 0，说明发现了一个尚未访问的岛屿，从(i,j)出发进行 DFS，计算整个岛屿的总价值。

3. DFS 计算岛屿总价值

定义递归函数f(i, j)，返回从(i,j)出发的整个岛屿的总价值。具体步骤：

先取出当前格子的值：
s = g r i d [ i ] [ j ] s = grid[i][j]s=grid[i][j]
将当前格子置为0，作为“已访问”标记，避免重复访问：
g r i d [ i ] [ j ] = 0 grid[i][j] = 0grid[i][j]=0
向上下左右四个方向扩展。对于每个邻居(x,y)：
- 若坐标在矩阵范围内；
- 且grid[x][y] != 0，说明仍是同一岛屿的陆地；
- 则递归调用f(x,y)，并把返回值累加到s。
返回s，即该岛屿的总价值。

由于每次访问后都把陆地置为0，每个陆地格子最多被访问一次。

4. 统计答案

主循环中：

if(g[i][j]&&f(i,j)%k==0){r++;}

利用&&的短路特性：先判断g[i][j]是否非零，只有非零时才调用f(i,j)。f(i,j)会一次性清空整个岛屿，因此后续扫描不会重复计算同一个岛屿。

若当前岛屿总价值满足f(i,j) % k == 0，答案r加一。

5. 数据类型

岛屿总价值最大可达：
m × n × 10 5 ≤ 10 5 × 10 5 = 10 10 m \times n \times 10^5 \le 10^5 \times 10^5 = 10^{10}m×n×105≤105×105=1010
超过int范围，因此递归函数返回类型和累加变量s必须使用long long。

6. 复杂度分析

每个陆地格子最多被访问一次，因此总时间复杂度为O ( m n ) O(mn)O(mn)；
最坏情况下整个矩阵为一个岛屿，递归深度可达O ( m n ) O(mn)O(mn)，空间复杂度为O ( m n ) O(mn)O(mn)。

总结

扫描矩阵，遇到非零格子就启动 DFS，收集整个四连通岛屿的权值和，并在访问过程中将陆地置零以避免重复。若该岛屿总价值能被k kk整除，则答案加一。整体是标准的网格连通块求和问题，时间复杂度为O ( m n ) O(mn)O(mn)，需注意使用long long防止总和溢出。

代码内容

classSolution{staticconstexprintD[4][2]={{0,1},{0,-1},{1,0},{-1,0}};public:intcountIslands(vector<vector<int>>&g,intk){intm=g.size(),n=g[0].size();autof=[&](thisauto&&f,inti,intj)->longlong{longlongs=g[i][j];g[i][j]=0;for(auto[a,b]:D){intx=i+a,y=j+b;if(0<=x&&x<m&&0<=y&&y<n&&g[x][y]){s+=f(x,y);}}returns;};intr=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(g[i][j]&&f(i,j)%k==0){r++;}}}returnr;}};