Submission #516708

#	Time	Username	Problem	Language	Result	Execution time	Memory
516708		KoD	Zoo (COCI19_zoo)	C++17	110 / 110	56 ms	6132 KiB

zoo

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int inf = std::numeric_limits<int>::max() / 2;

bool setmin(int& x, const int y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    const int V = (N + 2) * (M + 2);
    const auto cell = [&](const int i, const int j) {
        return i * (M + 2) + j;
    };
    vector<char> grid(V, '*');
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            std::cin >> grid[cell(i, j)];
        }
    }
    vector<int> dist(V, inf);
    std::deque<int> que;
    dist[cell(1, 1)] = 1;
    que.push_back(cell(1, 1));
    while (!que.empty()) {
        const int u = que.front();
        que.pop_front();
        for (const int v : {u + 1, u - 1, u + (M + 2), u - (M + 2)}) {
            if (grid[v] == '*') {
                continue;
            }
            if (grid[u] != grid[v]) {
                if (setmin(dist[v], dist[u] + 1)) {
                    que.push_back(v);
                }
            } else {
                if (setmin(dist[v], dist[u])) {
                    que.push_front(v);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < V; ++i) {
        if (grid[i] != '*') {
            ans = std::max(ans, dist[i]);
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65