제출 #724715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724715		rastervc	Mecho (IOI09_mecho)	C++17	70 / 100	301 ms	8520 KiB

mecho

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

constexpr int EMPTY = 0;
constexpr int BARRIER = 1;
constexpr int MECHO = 2;
constexpr int DANGER = 3;

constexpr int dx[] = { 0, 1, 0, -1 };
constexpr int dy[] = { 1, 0, -1, 0 };

inline bool test(
    int N, int S, int wait, pair<int, int> start, pair<int, int> finish,
    vector<pair<int, int>> trees, vector<pair<int, int>> hives
) {
    vector<vector<int>> mat(N + 2, vector<int>(N + 2, 0));
    queue<pair<int, int>> bees, pos;

    for (int i = 0; i <= N + 1; ++i)
        mat[i][0] = mat[0][i] = mat[i][N + 1] = mat[N + 1][i] = BARRIER;
    for (const auto[x, y] : trees)
        mat[x][y] = BARRIER;
    for (const auto[x, y] : hives) {
        mat[x][y] = DANGER;
        bees.emplace(x, y);
    }
    mat[start.first][start.second] = MECHO;
    pos.push(start);

    for (int time = 1; !bees.empty() && !pos.empty(); ++time) {
        if (time > wait) {
            for (int step = 1; step <= S; ++step) {
                const int sz = pos.size();
                for (int i = 0; i < sz; ++i) {
                    const auto[x0, y0] = pos.front();
                    pos.pop();

                    for (int j = 0; j < 4; ++j) {
                        const int x1 = x0 + dx[j];
                        const int y1 = y0 + dy[j];
                        if (mat[x1][y1] == EMPTY) {
                            mat[x1][y1] = MECHO;
                            pos.emplace(x1, y1);
                        }
                    }
                }
            }
        }

        const int sz = bees.size();
        for (int i = 0; i < sz; ++i) {
            const auto[x0, y0] = bees.front();
            bees.pop();

            for (int j = 0; j < 4; ++j) {
                const int x1 = x0 + dx[j];
                const int y1 = y0 + dy[j];
                if (mat[x1][y1] == EMPTY || mat[x1][y1] == MECHO) {
                    mat[x1][y1] = DANGER;
                    bees.emplace(x1, y1);
                }
            }
        }

        if (mat[finish.first][finish.second] == MECHO)
            return true;
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<pair<int, int>> trees, hives;
    pair<int, int> start, finish;
    int N, S;
    char ch;

    cin >> N >> S;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> ch;
            if (ch == 'T')
                trees.emplace_back(i, j);
            else if (ch == 'H')
                hives.emplace_back(i, j);
            else if (ch == 'M')
                start = { i, j };
            else if (ch == 'D')
                finish = { i, j };
        }
    }

    int l = 0, r = N * N, ans = -1;
    while (l <= r) {
        const int mid = (l + r) >> 1;
        if (test(N, S, mid, start, finish, trees, hives)) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }

    cout << ans;
    return 0;
}

• Subtask 1: 70 / 100