제출 #1349895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1349895		bestzu	Mecho (IOI09_mecho)	C++20	89 / 100	110 ms	6260 KiB

mecho

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

using pii = pair<int,int>;

const int N = 810;
const int INF = 1e9;

int n, s;
char a[N][N];
int distBee[N][N];
int distMecho[N][N];

int di[] = {-1, 0, 0, 1};
int dj[] = {0, -1, 1, 0};

int si, sj, ti, tj;

bool ok(int t) {
    
    if (t >= distBee[si][sj]) return false;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            distMecho[i][j] = -1;
        }
    }

    queue<pii> q;
    q.push({si, sj});
    distMecho[si][sj] = 0;

    while (!q.empty()) {
        auto [ui, uj] = q.front();
        q.pop();

        if (ui == ti && uj == tj) return true;

        for (int k = 0; k < 4; k++) {
            int vi = ui + di[k];
            int vj = uj + dj[k];

            if (vi < 0 || vi >= n || vj < 0 || vj >= n) continue;
            if (a[vi][vj] != 'G' && a[vi][vj] != 'D') continue;
            if (distMecho[vi][vj] != -1) continue;

            int step = distMecho[ui][uj] + 1;

            int currentTime = t * s + step;

            if (a[vi][vj] != 'D') {
                if (currentTime >= distBee[vi][vj]) continue;
            }

            distMecho[vi][vj] = step;
            q.push({vi, vj});
        }
    }

    return false;
}

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

    cin >> n >> s;

    queue<pii> qb;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            distBee[i][j] = INF;

            if (a[i][j] == 'H') {
                qb.push({i, j});
                distBee[i][j] = 0;
            }
            if (a[i][j] == 'M') {
                si = i;
                sj = j;
            }
            if (a[i][j] == 'D') {
                ti = i;
                tj = j;
            }
        }
    }

    // BFS ของผึ้ง (หน่วย = step ของ Mecho)
    while (!qb.empty()) {
        auto [ui, uj] = qb.front();
        qb.pop();

        for (int k = 0; k < 4; k++) {
            int vi = ui + di[k];
            int vj = uj + dj[k];

            if (vi < 0 || vi >= n || vj < 0 || vj >= n) continue;

            if (a[vi][vj] == 'G' || a[vi][vj] == 'M') {
                if (distBee[vi][vj] > distBee[ui][uj] + s) {
                    distBee[vi][vj] = distBee[ui][uj] + s;
                    qb.push({vi, vj});
                }
            }
        }
    }

    int l = 0, r = n * n, ans = -1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (ok(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 89 / 100