Submission #74291821

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef unsigned __int128 ulll;

void solve() {
    int h,w;
    cin >> h >> w;
    vector<vector<char>> graph(h,vector<char>(w));
    vector<vector<int>> vis(h,vector<int>(w,0));
    for (int i = 0;i < h;i++) {
        for (int j = 0;j < w;j++) {
            cin >> graph[i][j];
            if (graph[i][j] == '#') {
                vis[i][j] = -1;
            }
        }
    }
    vector<int> di = {1,-1,0,0};
    vector<int> dj = {0,0,1,-1};
    queue<pair<int,int>> bfs;
    ll ans = 0;
    for (int i = 0;i < h;i++) {
        for (int j = 0;j < w;j++) {
            bool found = false;
            if (graph[i][j] == '.' && vis[i][j] == 0) {
                bfs.push({i,j});
                vis[i][j] = -1;
                found = true;
            }
            bool is = false;
            while(!bfs.empty()) {
                auto &[ii,jj] = bfs.front();
                bfs.pop();
                for (int i = 0;i < 4;i++) {
                    int cur_i = ii + di[i];
                    int cur_j = jj + dj[i];
                    if (cur_i < 0 || cur_i >= h || cur_j < 0 || cur_j >= w) {
                        if (!is) {
                            is = true;
                        }
                        continue;
                    }
                    if (vis[cur_i][cur_j] == -1) {
                        continue;
                    }
                    vis[cur_i][cur_j] = -1;
                    bfs.push({cur_i,cur_j});
                }
            }
            if (found && !is) {
                ans++;
            }
        }
    }
    cout << ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Submission Info

Judge Result