CSES - Shared codeLink to this code:
https://cses.fi/paste/879c322195ad173f301fed/
#include <bits/stdc++.h>
using namespace std;
vector<int> d = {1, 0, 0, 1, -1, 0, 0, -1};
int n, m;
bool valid(int r, int c, vector<vector<char>> &g) {
if (r < 0 || c < 0 || r >= n || c >= m || g[r][c] == '#') {
return false;
}
return true;
}
void dfs(int r, int c, vector<vector<char>> &g) {
g[r][c] = '#';
for (int i = 0; i < 8; i += 2) {
if (valid(r + d[i], c + d[i + 1], g)) {
dfs(r + d[i], c + d[i + 1], g);
}
}
}
void bfs(int rs, int cs, vector<vector<char>> &g) {
queue<vector<int>> q;
g[rs][cs] = '#';
q.push({rs, cs});
while (q.size() > 0) {
vector<int> cell = q.front();
q.pop();
int r = cell[0], c = cell[1];
for (int i = 0; i < 8; i += 2) {
if (valid(r + d[i], c + d[i + 1], g)) {
g[r + d[i]][c + d[i + 1]] = '#';
q.push({r + d[i], c + d[i + 1]});
}
}
}
}
int main() {
cin >> n >> m;
vector<vector<char>> g(n, vector<char> (m));
string str;
getline(cin, str);
for (int i = 0; i < n; i++) {
getline(cin, str);
for (int j = 0; j < m; j++) {
g[i][j] = str[j];
}
}
int count;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (g[i][j] == '.') {
bfs(i, j, g);
count++;
}
}
}
cout << count;
}