Submission #74283679

---

Source Code Expand

/*
Author:
    interstellar
site:
    AtGuesses.com
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define ll long long
#define umap unordered_map
#define uset unordered_set
constexpr int inf = (int)1e9 + 5;
constexpr ll  llinf = (ll)1e18 + 5;
// constexpr int mod = ((int)1e9+7);
constexpr int mod = 998244353;

using namespace std;
#define vll vector<ll>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vvi vector<vi>
#define vvll vector<vll>

void test_case(){
    int h, w;
    cin >> h >> w;

    vector<string> A(h);
    for (auto &p : A)cin >> p;
    vector<vi> vis(h, vi(w));
    int cc = 1;
    auto bfs = [&](int i, int j){
        queue<pair<int, int>> q;
        q.push({i, j});
        vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.empty()){
            auto &[r, c] = q.front();
            q.pop();
            if (vis[r][c])continue;
            vis[r][c] = cc;
            for (auto &[dr, dc] : dir){
                if (r + dr >= h || c + dc >= w || r + dr < 0 || c + dc < 0 || A[r + dr][c + dc] == '#')continue;
                q.push({r + dr, c + dc});
            }
        }
    };

    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (vis[i][j] || A[i][j] == '#')continue;
            bfs(i, j);
            cc++;
        }
    }
    set<int> s;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++){
            if (i == 0 || i == h - 1 || j == 0 || j == w- 1){
                if (A[i][j] == '.')s.insert(vis[i][j]);
            }
        }
    }
    cout << cc - int(s.size()) - 1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    test_case();

    return 0;
}
/*
*/

Submission Info

Judge Result