Submission #69665908

---

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define int long long
#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int, int> PI;
typedef pair<int, pair<int, int>> PII;
static const int INF = 1010000000000000017LL;
static const double eps = 1e-12;
static const double pi = 3.14159265358979323846;
static const int dx[4] = {1, -1, 0, 0};
static const int dy[4] = {0, 0, 1, -1};
static const int ddx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
static const int ddy[8] = {0, 0, 1, -1, 1, -1, 1, -1};

template <class T>
inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int H, W;

signed main() {
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; ++i) {
        cin >> S[i];
    }
    int k = 0;
    vector<PI> P;
    while (true) {
        vector<PI> Q;
        if (k == 0) {
            for (int i = 0; i < H; ++i) {
                for (int j = 0; j < W; ++j) {
                    if (S[i][j] == '.') {
                        int cnt = 0;
                        for (int k = 0; k < 4; ++k) {
                            int ni = i + dy[k];
                            int nj = j + dx[k];
                            if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
                            if (S[ni][nj] == '#') {
                                cnt++;
                            }
                        }
                        if (cnt == 1) {
                            Q.push_back({i, j});
                        }
                    }
                }
            }
        } else {
            for (auto p : P) {
                int i = p.first;
                int j = p.second;
                for (int k = 0; k < 4; ++k) {
                    int ni = i + dy[k];
                    int nj = j + dx[k];
                    if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
                    if (S[ni][nj] == '#') continue;
                    int cnt = 0;
                    for (int l = 0; l < 4; ++l) {
                        int nni = ni + dy[l];
                        int nnj = nj + dx[l];
                        if (nni < 0 || nni >= H || nnj < 0 || nnj >= W) continue;
                        if (S[nni][nnj] == '#') {
                            cnt++;
                        }
                    }
                    if (cnt == 1) {
                        Q.push_back({ni, nj});
                    }
                }
            }
        }
        if (Q.size() == 0) break;
        for (auto p : Q) {
            S[p.first][p.second] = '#';
        }
        // cout << "-----" << endl;
        // for (int i = 0; i < H; ++i) {
        //     cout << S[i] << endl;
        // }
        // cout << "-----" << endl;
        P = Q;
        k++;
    }
    int ans = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == '#') {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Submission Info

Judge Result