Submission #3725095

---

Source Code Expand

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
bool hori(int di, int dj) { return abs(di) == 0 and abs(dj) == 1; }
bool vert(int di, int dj) { return abs(di) == 1 and abs(dj) == 0; }
bool diag(int di, int dj) { return abs(di) == 1 and abs(dj) == 1; }
bool can(int di, int dj) { return hori(di, dj) or vert(di, dj) or diag(di, dj); }
template <typename signature> using f = const function<signature>&;
void flood(vector<vector<bool>>& a, f<bool(int, int)> can, f<void(int, int, int, int)> f) {
    int n = a.size() - 2, m = a[0].size() - 2;
    vector<vector<bool>> vis(n + 2, vector<bool>(m + 2));
    function<void(int, int, int, int)> dfs = [&](int i, int j, int from_i, int from_j) {
        if(a[i][j] and not vis[i][j]) {
            f(i, j, from_i, from_j);
            vis[i][j] = true;
            for(int di = -1; di <= 1; di++) {
                for(int dj = -1; dj <= 1; dj++) {
                    if(can(di, dj)) {
                        dfs(i + di, j + dj, i, j);
                    }
                }
            }
        }
    };
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(not vis[i][j]) {
                dfs(i, j, 0, 0);
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    const int n = 10;
    vector<vector<bool>> a(n + 2, vector<bool>(n + 2));
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for(int j = 1; j <= n; j++) {
            a[i][j] = s[j - 1] == 'o';
        }
    }
    vector<vector<int>> component(n + 2, vector<int>(n + 2));
    int id = 0;
    flood(a, can, [&](int i, int j, int from_i, int from_j) {
        component[i][j] = from_i ? component[from_i][from_j] : ++id;
    });
    bool can = id == 1;
    for(int i = 1; i <= n and not can; i++) {
        for(int j = 1; j <= n and not can; j++) {
            if(not a[i][j]) {
                set<int> neighbors;
                for(int di = -1; di <= 1; di++) {
                    for(int dj = -1; dj <= 1; dj++) {
                        if((hori(di, dj) or vert(di, dj)) and a[i + di][j + dj]) {
                            neighbors.insert(component[i + di][j + dj]);
                        }
                    }
                }
                can |= neighbors.size() == id;
            }
        }
    }
    cout << (can ? "YES" : "NO") << endl;
    return 0;
}

Submission Info

Judge Result