[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 來記錄
