Alex and Animal Rights

    1#include <bits/stdc++.h>
    2using namespace std;
    3vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    4void bfs(int i, int j, vector<vector<char>> &g, vector<vector<bool>> & vis){
    5    vis[i][j] = 1;
    6    queue<pair<int, int>> q;
    7    q.push({i, j});
    8    while(!q.empty()){
    9        auto[r, c] = q.front(); q.pop();
    10        for(auto[rr, cc] : dir){
    11            int nr = r + rr, nc = c + cc;
    12            if(nr >= 0 && nr < g.size() && nc >= 0 && nc < g[0].size() && !vis[nr][nc] && g[nr][nc] != '#'){
    13                q.push({nr, nc});
    14                vis[nr][nc] = 1;
    15            }
    16        }
    17    }
    18}
    19int main(){
    20    ios::sync_with_stdio(0); cin.tie(0);
    21    int row, col; cin >> row >> col;
    22    vector<vector<char>> g(row, vector<char>(col));
    23    for(int i = 0; i < row; i++){
    24        for(int j = 0; j < col; j++){
    25            cin >> g[i][j];
    26        }
    27    }
    28    int ans = 0;
    29    vector<vector<bool>> vis(row, vector<bool>(col));
    30    for(int i = 0; i < row; i++){
    31        for(int j = 0; j < col; j++){
    32            if(!vis[i][j] && g[i][j] == 'M'){
    33                bfs(i, j, g, vis);
    34                ans++;
    35            }
    36        }
    37    }
    38    cout << ans << '\n';
    39    return 0;
    40}