Submission #74278467

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

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

    int h, w;
    cin >> h >> w;
    vector<string> g(h);
    for (int i = 0; i < h; i++) cin >> g[i];

    int ans = 0;
    vector<int> dx = {-1, 0, 1,  0};
    vector<int> dy = { 0, 1, 0, -1};
    vector<vector<bool>> f(h, vector<bool>(w, false));
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (g[i][j] == '.' && !f[i][j]) {
        int x1 = i, x2 = i, y1 = j, y2 = j;
        queue<pair<int, int>> q;
        q.push({i, j}), f[i][j] = true;
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; i++) {
                int u = x + dx[i], v = y + dy[i];
                if (u < 0 || u >= h || v < 0 || v >= w || g[u][v] == '#' || f[u][v]) continue;
                q.push({u, v}), f[u][v] = true;
                x1 = min(x1, u), x2 = max(x2, u);
                y1 = min(y1, v), y2 = max(y2, v);
            }
        }
        if (x1 == 0 || x2 == h - 1 || y1 == 0 || y2 == w - 1) continue;
        ans++;
    }
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result