Submission #1242142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242142		rhm_gan	Mecho (IOI09_mecho)	C++20	15 / 100	1098 ms	131072 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif

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

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

    int n, s;
    cin >> n >> s;

    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int endx = 0, endy = 0, stx = 0, sty = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == 'M') {
                stx = i;
                sty = j;
            }
            if (a[i][j] == 'D') {
                endx = i;
                endy = j;
            }
        }
    }


    vector<vector<int>> res(n, vector<int>(n, 2e9));
    vector<vector<bool>> vis(n, vector<bool>(n));

    res[stx][sty] = 0;
    queue<pair<int, int>> que;
    que.emplace(stx, sty);

    while (!que.empty()) {
        auto [x, y] = que.front();
        vis[x][y] = 1;
        que.pop();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (abs(i - x) + abs(j - y) <= s && !vis[i][j] && a[i][j] != 'T') {
                    res[i][j] = min(res[i][j], res[x][y] + 1);
                    que.emplace(i, j);
                }
            }
        }
    }

    auto good = [&](int k) {
        queue<array<int, 3>> que;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i][j] == 'H') {
                    que.push({i, j, 0});
                }
            }
        }
        vector<vector<bool>> vis(n, vector<bool>(n));
        auto valid = [&](int x, int y) {
            return (0 <= x && x < n && 0 <= y && y < n && !vis[x][y] && a[x][y] != 'T' && a[x][y] != 'D');
        };

        while (!que.empty()) {
            auto [x, y, d] = que.front();
            vis[x][y] = true;
            que.pop();
            if (d == k) continue;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (valid(nx, ny)) {
                    que.push({nx, ny, d + 1});
                }
            }
        }

        vector<vector<int>> dist(n, vector<int>(n, 1e9));
        queue<pair<int, int>> q;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j]) {
                    dist[i][j] = 0;
                    q.emplace(i, j);
                    vis[i][j] = false;
                }
            }
        }

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            vis[x][y] = 1;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (valid(nx, ny)) {
                    q.emplace(nx, ny);
                    dist[nx][ny] = min(dist[nx][ny], dist[x][y] + 1);
                }
            }
        }

        fill(vis.begin(), vis.end(), vector<bool>(n, false));

        q.emplace(stx, sty);
        while (!q.empty()) {
            auto [x, y] = q.front();
            vis[x][y] = 1;
            q.pop();
            if (x == endx && y == endy) {
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n && !vis[nx][ny] && a[nx][ny] != 'T' && dist[nx][ny] > res[nx][ny]) {
                    q.emplace(nx, ny);
                }
            }
        }

        return false;
    };

    if (!good(0)) {
        cout << -1 << '\n';
        return 0;
    }

    int l = 0, r = 1e9;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (good(m)) {
            l = m;
        }
        else {
            r = m;
        }
    }

    cout << l << '\n';


    return 0;
}

• Subtask 1: 15 / 100