3619. Count Islands With Total Value Divisible by K

/**
 * Problem: LeetCode 3619 - Count Islands With Total Value Divisible by K
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int countIslands(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        int count = 0;
        int[] stack = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) continue;
                long sum = 0;
                int top = 0;
                stack[top++] = i * n + j;
                sum += grid[i][j];
                grid[i][j] = 0;
                while (top > 0) {
                    int cur = stack[--top];
                    int r = cur / n, c = cur % n;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d], nc = c + dc[d];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] == 0) continue;

                        sum += grid[nr][nc];
                        grid[nr][nc] = 0;
                        stack[top++] = nr * n + nc;
                    }
                }
                if (sum % k == 0) count++;
            }
        }
        return count;
    }
}

"""
Problem: LeetCode 3619 - Count Islands With Total Value Divisible by K
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        dr = [1, -1, 0, 0]
        dc = [0, 0, 1, -1]
        count = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    continue
                total_sum = grid[i][j]
                grid[i][j] = 0
                stack = [i * n + j]

                while stack:
                    cur = stack.pop()
                    r, c = divmod(cur, n)
                    for d in range(4):
                        nr, nc = r + dr[d], c + dc[d]
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0:
                            total_sum += grid[nr][nc]
                            grid[nr][nc] = 0
                            stack.append(nr * n + nc)

                if total_sum % k == 0:
                    count += 1

        return count

/**
 * Problem: LeetCode 3619 - Count Islands With Total Value Divisible by K
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>

using namespace std;

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) continue;
                long long sum = grid[i][j];
                int top = 0;
                stack[top++] = i * n + j;
                grid[i][j] = 0;

                while (top > 0) {
                    int cur = stack[--top];
                    int r = cur / n, c = cur % n;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d], nc = c + dc[d];
                        if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] == 0) continue;

                        sum += grid[nr][nc];
                        grid[nr][nc] = 0;
                        stack[top++] = nr * n + nc;
                    }
                }
                if (sum % k == 0) count++;
            }
        }
        return count;
    }
};

/**
 * Problem: LeetCode 3619 - Count Islands With Total Value Divisible by K
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var countIslands = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const dr = [1, -1, 0, 0];
    const dc = [0, 0, 1, -1];
    let count = 0;
    const stack = new Int32Array(m * n);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 0) continue;

            let sum = grid[i][j];
            let top = 0;
            stack[top++] = i * n + j;
            grid[i][j] = 0;

            while (top > 0) {
                const cur = stack[--top];
                const r = Math.floor(cur / n);
                const c = cur % n;

                for (let d = 0; d < 4; d++) {
                    const nr = r + dr[d];
                    const nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] === 0) continue;

                    sum += grid[nr][nc];
                    grid[nr][nc] = 0;
                    stack[top++] = nr * n + nc;
                }
            }

            if (sum % k === 0) {
                count++;
            }
        }
    }

    return count;
};