目标
给你一个 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^5
- 0 <= grid[i][j] <= 10^6
- 1 <= k < = 10^6
思路
有一个 m x n 矩阵 grid 和一个正整数 k，定义正整数的格子为陆地，陆地四周相连组成的区域称为岛屿，岛屿的总价值为所有单元格的值之和。求矩阵中总价值能被 k 整除的岛屿数量。
枚举所有格子，以它为起点 dfs 矩阵，返回总价值，跳过已访问过的格子。
代码
/**
* @date 2026-10-26 9:44
*/
public class CountIslands3619 {
int[][] directions = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public int countIslands(int[][] grid, int k) {
int m = grid.length;
int n = grid[0].length;
int res = 0;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
visited[i][j] = true;
} else if (!visited[i][j] && dfs(i, j, grid, visited) % k == 0) {
res++;
}
}
}
return res;
}
public long dfs(int i, int j, int[][] grid, boolean[][] visited) {
int m = grid.length;
int n = grid[0].length;
visited[i][j] = true;
long res = grid[i][j];
for (int[] d : directions) {
int ni = i + d[0];
int nj = j + d[1];
if (ni >= 0 && nj >= 0 && ni < m && nj < n && grid[i][j] > 0 && !visited[ni][nj]) {
res += dfs(ni, nj, grid, visited);
}
}
return res;
}
}
性能
