Submission #1340095

#TimeUsernameProblemLanguageResultExecution timeMemory
1340095model_codeSirologija (COI24_sirologija)C++20
100 / 100
132 ms51444 KiB
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

namespace {

class DisjointSet {
public:
    explicit DisjointSet(int n) : parent_(n, -1), size_(n, 1), touches_boundary_(n, 0) {}

    void activate(int v, bool touches_boundary) {
        parent_[v] = v;
        touches_boundary_[v] = static_cast<unsigned char>(touches_boundary);
    }

    bool active(int v) const {
        return parent_[v] != -1;
    }

    int find(int v) {
        if (parent_[v] == v) {
            return v;
        }
        return parent_[v] = find(parent_[v]);
    }

    void unite(int a, int b) {
        if (!active(a) || !active(b)) {
            return;
        }
        a = find(a);
        b = find(b);
        if (a == b) {
            return;
        }
        if (size_[a] < size_[b]) {
            std::swap(a, b);
        }
        parent_[b] = a;
        size_[a] += size_[b];
        touches_boundary_[a] = static_cast<unsigned char>(touches_boundary_[a] || touches_boundary_[b]);
    }

    bool touches_boundary(int v) {
        return touches_boundary_[find(v)] != 0;
    }

    bool is_root(int v) const {
        return parent_[v] == v;
    }

private:
    std::vector<int> parent_;
    std::vector<int> size_;
    std::vector<unsigned char> touches_boundary_;
};

}  // namespace

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::string> grid(n);
    for (std::string& row : grid) {
        std::cin >> row;
    }

    const int total = n * m;
    auto id = [m](int r, int c) {
        return r * m + c;
    };

    std::vector<unsigned char> from_start(total, 0);
    std::vector<unsigned char> to_finish(total, 0);

    if (grid[0][0] == '.') {
        from_start[id(0, 0)] = 1;
    }
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            if (grid[r][c] != '.') {
                continue;
            }
            if (r > 0 && from_start[id(r - 1, c)]) {
                from_start[id(r, c)] = 1;
            }
            if (c > 0 && from_start[id(r, c - 1)]) {
                from_start[id(r, c)] = 1;
            }
        }
    }

    if (grid[n - 1][m - 1] == '.') {
        to_finish[id(n - 1, m - 1)] = 1;
    }
    for (int r = n - 1; r >= 0; --r) {
        for (int c = m - 1; c >= 0; --c) {
            if (grid[r][c] != '.') {
                continue;
            }
            if (r + 1 < n && to_finish[id(r + 1, c)]) {
                to_finish[id(r, c)] = 1;
            }
            if (c + 1 < m && to_finish[id(r, c + 1)]) {
                to_finish[id(r, c)] = 1;
            }
        }
    }

    std::vector<unsigned char> usable(total, 0);
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            usable[id(r, c)] = static_cast<unsigned char>(from_start[id(r, c)] && to_finish[id(r, c)]);
        }
    }

    DisjointSet dsu(total);
    const int dr[4] = {-1, -1, -1, 0};
    const int dc[4] = {-1, 0, 1, -1};

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            const int v = id(r, c);
            if (usable[v]) {
                continue;
            }

            const bool boundary = (r == 0 || r == n - 1 || c == 0 || c == m - 1);
            dsu.activate(v, boundary);

            for (int dir = 0; dir < 4; ++dir) {
                const int nr = r + dr[dir];
                const int nc = c + dc[dir];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) {
                    continue;
                }
                const int u = id(nr, nc);
                if (!usable[u]) {
                    dsu.unite(v, u);
                }
            }
        }
    }

    int answer = usable[id(0, 0)] ? 1 : 0;
    for (int v = 0; v < total; ++v) {
        if (!dsu.active(v) || !dsu.is_root(v)) {
            continue;
        }
        if (!dsu.touches_boundary(v)) {
            ++answer;
        }
    }

    std::cout << answer << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...