Submission #689576

#	Time	Username	Problem	Language	Result	Execution time	Memory
689576		tcmmichaelb139	Mecho (IOI09_mecho)	C++17	21 / 100	110 ms	8872 KiB

mecho

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

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

struct node {
    int x, y;
    int mx;
    int step;
    int dist;

    bool operator<(const node& rhs) const {
        return mx < rhs.mx;
    }
};

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

    int n, s;
    cin >> n >> s;
    vector<vector<char>> ar(n, vector<char>(n));
    pair<int, int> start, end;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> ar[i][j];
            if (ar[i][j] == 'M')
                start = {i, j};
            else if (ar[i][j] == 'D')
                end = {i, j};
        }

    auto bee_dist_gen = [&]() {
        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 (ar[i][j] == 'H')
                    q.push({i, j}), dist[i][j] = 0;

        while (!q.empty()) {
            pair<int, int> v = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = v.first + dx[i], ny = v.second + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                if (ar[nx][ny] == 'T') continue;
                if (dist[nx][ny] <= dist[v.first][v.second] + 1) continue;

                dist[nx][ny] = dist[v.first][v.second] + 1;
                q.push({nx, ny});
            }
        }

        return dist;
    };

    vector<vector<int>> bee_dist = bee_dist_gen();

    vector<vector<bool>> vis(n, vector<bool>(n, false));

    priority_queue<node> q;
    q.push({start.first, start.second, bee_dist[start.first][start.second] - 1, 0, 0});

    while (!q.empty()) {
        node v = q.top();
        q.pop();

        if (vis[v.x][v.y]) continue;
        vis[v.x][v.y] = true;
        /* cout << v.x << ' ' << v.y << ' ' << v.mx << ' ' << v.step << ' ' << v.dist << '\n'; */
        if (end.first == v.x && end.second == v.y) {
            cout << v.mx << '\n';
            return 0;
        }

        if (v.step == 0)
            v.dist++;

        for (int i = 0; i < 4; i++) {
            int nx = v.x + dx[i], ny = v.y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (ar[nx][ny] == 'T') continue;
            if (bee_dist[nx][ny] < v.dist) continue;
            if (vis[nx][ny]) continue;

            q.push({nx, ny, min(v.mx, bee_dist[nx][ny] - v.dist), (v.step + 1) % s, v.dist});
        }
    }
    cout << -1 << '\n';
}

/* 7 3 */
/* TTTTTTT */
/* TTTTTTT */
/* TGGGGGT */
/* MGGGGGD */
/* TGGGGGT */
/* TGGGGGT */
/* TGHHGGT */

• Subtask 1: 21 / 100