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

发布时间：2026/10/28 10:21:03
总价值可以被 K 整除的岛屿数目【力扣LeetCode 每日一题】

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

网页链接

力扣LeetCode

力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！

题目描述

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

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

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

输入描述

一个m × n m \times nm×n的矩阵grid和一个正整数k kk。

输出描述

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

示例 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 55整除，而红色高亮显示的岛屿则不能。

示例 2

输入：

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

输出：

6

解释：

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

数据范围

解题思路

本题是网格连通块搜索 + 连通块权值求和问题。矩阵中非零正整数表示陆地，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. 遍历与发现新岛屿

从左上到右下扫描矩阵：

3. DFS 计算岛屿总价值

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

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

总结

扫描矩阵，遇到非零格子就启动 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;}};