Submission #74293394

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include<queue>

using namespace std;

vector<int> dx = {0, 0, -1, 1};
vector<int> dy = {1, -1, 0, 0};
void solve() {
    
    int n, m; cin >> n >> m;

    vector<string> grid(n);

    for(auto &i: grid){
        cin >> i;
    }

    queue<pair<int, int>> q;

    for(int i = 0; i < n; i++){
        if(grid[i][0] == '.'){
            q.push({i, 0});
            grid[i][0] = '#';
        }

        if(grid[i][m-1] == '.'){
            q.push({i, m - 1});
            grid[i][m-1] = '#';
        }
    }

    for(int j = 0; j < m; j++){
        if(grid[0][j] == '.'){
            q.push({0, j});
            grid[0][j] = '#';
        }
        if(grid[n-1][j] == '.'){
            q.push({n-1, j});
            grid[n-1][j] = '#';
        }
        
    }

    while(!q.empty()){
        pair<int, int> u = q.front();
        q.pop();

        for(int d = 0; d < 4; d++){
            int nx = u.first + dx[d];
            int ny = u.second + dy[d];

            if(nx >= n || nx < 0 || ny >= m || ny < 0) continue;

            if(grid[nx][ny] == '#') continue;

            q.push({nx, ny});
            grid[nx][ny] = '#';
        }
    }

    auto dfs = [&](int x, int y, auto && self) -> void {
        
        grid[x][y] = '#';
        for(int d = 0; d < 4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];

            if(nx >= n || nx < 0 || ny >= m || ny < 0) continue;

            if(grid[nx][ny] == '#') continue;

            self(nx, ny, self);
        }
    };

    int ans = 0;
    for(int i = 1; i < n-1; i++){
        for(int j = 1; j < m - 1; j++){
            if(grid[i][j] == '#') continue;
            dfs(i, j, dfs);
            ans++;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

Submission Info

Judge Result