IOI '09 P6 - Mecho

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> g;
vector<vector<bool>> mechoReached, beesReached;
inline bool mechoCanAccess(int i, int j) {
    return g[i][j] != 'T' && !beesReached[i][j];
}
inline bool beesCanAccess(int i, int j) {
    return g[i][j] != 'T' && g[i][j] != 'D';
}
pair<int, int> dir[4]{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, s; cin >> n >> s;
    g.resize(n);
    for (string &row : g) cin >> row;

    int mechoStartI, mechoStartJ, mechoEndI, mechoEndJ;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (g[i][j] == 'M') mechoStartI = i, mechoStartJ = j;
            else if (g[i][j] == 'D') mechoEndI = i, mechoEndJ = j;
        }
    }

    auto canWait = [&](int time) -> bool {
        // check if Mecho can wait time seconds
        mechoReached.assign(n, vector<bool>(n, false));
        beesReached.assign(n, vector<bool>(n, false));
        vector<pair<int, int>> beesNew, mechoNew;
        auto inside = [&](int i, int j) {
            return 0 <= i && i < n && 0 <= j && j < n;
        };

        bool beesStillChanging = true, mechoStillChanging = true;
        auto moveBees = [&]() {
            vector<pair<int, int>> beesNew2;
            for (auto [i, j] : beesNew) {
                for (auto [di, dj] : dir) {
                    int ii = i+di, jj = j+dj;
                    if (inside(ii, jj) && !beesReached[ii][jj] && beesCanAccess(ii, jj)) {
                        beesReached[ii][jj] = true;
                        beesNew2.emplace_back(ii, jj);
                    }
                }
            }
            swap(beesNew, beesNew2);
            if (beesNew.empty()) beesStillChanging = false;
        };
        auto moveMecho = [&]() {
            vector<pair<int, int>> mechoNew2;
            for (auto [i, j] : mechoNew) {
                if (beesReached[i][j]) continue; // if bees reached after mecho reached
                for (auto [di, dj] : dir) {
                    int ii = i+di, jj = j+dj;
                    if (inside(ii, jj) && !mechoReached[ii][jj] && mechoCanAccess(ii, jj)) {
                        mechoReached[ii][jj] = true;
                        mechoNew2.emplace_back(ii, jj);
                    }
                }
            }
            swap(mechoNew, mechoNew2);
            if (mechoNew.empty()) mechoStillChanging = false;
        };

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (g[i][j] == 'H') beesReached[i][j] = true, beesNew.emplace_back(i, j);
            }
        }
        for (int i = 0; i < time; ++i) moveBees();

        if (beesReached[mechoStartI][mechoStartJ]) return false;

        mechoReached[mechoStartI][mechoStartJ] = true, mechoNew.emplace_back(mechoStartI, mechoStartJ);
        while (mechoStillChanging && !mechoReached[mechoEndI][mechoEndJ]) {
            // move mecho
            for (int i = 0; i < s && mechoStillChanging; ++i) moveMecho();

            // move bees
            moveBees();
        }
        return mechoReached[mechoEndI][mechoEndJ];
    };

    int left = -1, right = n*n; // binary search on answer
    while (left + 1 < right) {
        int mid = (left + right) / 2;
        // check if Mecho can wait mid seconds
        if (canWait(mid)) left = mid;
        else right = mid;
    }
    cout << left << endl;
    return 0;
}