3619. Count Islands With Total Value Divisible by K

[Medium] 解法 : BFS

題意 :

給定一個二維陣列，元素為整數，與一個整數 k。其中被 0 圍起來的整數區塊為 island，island value 為區塊內元素數值的總和。一個合法的小島是其 value 可以被 k 整除，求出符合此條件的所有小島，並將 value 加總回傳。

小島範例如下圖有顏色的區塊

圖片來源 : https://leetcode.com/problems/count-islands-with-total-value-divisible-by-k/description/

解題思路 :

走訪陣列中每個元素，如果該元素為 0 則往 <上、下、左、右>進行 BFS，並將 BFS 走訪到的元素標記成 0 避免重複拜訪，如此走訪可以得到一個小島的值，最後小島的值如果符合條件就將其記錄下來。

class Solution {

public:

    int bfs(vector<vector<int>>& grid, int i, int j, int k) {

        int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        int n = grid.size(), m = grid[0].size();
        int count = grid[i][j] % k;

        queue<pair<int, int>> q;
        q.push({i, j});
        grid[i][j] = 0;

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; ++d) {
                int nx = x + dir[d][0];
                int ny = y + dir[d][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny]) {
                    count = (count + grid[nx][ny]) % k;
                    grid[nx][ny] = 0;
                    q.push({nx, ny});
                }
            }
        }
        return count;
    }

    int countIslands(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] && bfs(grid, i, j, k) == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Extra :

測資的值有機會會讓 count 在加總的過程超出 int 範圍，所以可以在每次加總就取 mod 或是用 long long 來記錄