Counting Rooms

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4pair<int, int> dir[]={
5  {0, 1},
6  {1, 0},
7  {0, -1},
8  {-1, 0}
9};
10signed main(){
11  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12  int N,M; cin>>N>>M;
13
14  bool vis[N][M]; memset(vis, 0, sizeof(vis));
15  for(int i=0; i<N; ++i) for(int j=0; j<M; ++j) {
16    char c; cin>>c;
17    vis[i][j]=c=='#';
18  }
19
20  int ans = 0;  // # of c.c
21  queue<pair<int,int>> q;
22  for(int i=0; i<N; ++i) for(int j=0; j<M; ++j) {
23    if(vis[i][j]) continue;
24    vis[i][j] = 1;
25    ++ans;
26    q.emplace(i, j);
27    while(q.size()){
28      pair<int, int> cur = q.front(); q.pop();
29      for(auto &p:dir){
30        int nxi = cur.first + p.first;
31        int nxj = cur.second + p.second;
32        if (0 <= nxi && nxi < N && 0 <= nxj && nxj < M && !vis[nxi][nxj]){
33          q.emplace(nxi,nxj);
34          vis[nxi][nxj] = 1;
35        }
36      }
37    }
38  }
39  cout << ans << '\n';
40  return 0;
41}