제출 #1314700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314700		menkh	Mecho (IOI09_mecho)	C++17	35 / 100	1096 ms	7560 KiB

mecho

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

#define ll long long
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)

#define MAX 805
const int INF = 1000000000 + 10;
char forest[MAX][MAX];
int bear[MAX][MAX];
int ong[MAX][MAX];
bool vis[MAX][MAX];
int n, S;

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

int sx, sy, tx, ty;

bool check(int k) {
    if (k >= ong[sx][sy]) return false;

    FOR(i,1,n) FOR(j,1,n) bear[i][j] = INF;

    queue<pair<int,int>> q;
    bear[sx][sy] = k;
    q.push({sx, sy});

    while (!q.empty()) {
        auto it = q.front(); q.pop();
        int x = it.first, y = it.second;

        FOR(i,1,n) FOR(j,1,n) vis[i][j] = false;

        queue<pair<pair<int,int>,int>> qlocal;
        qlocal.push({{x, y}, 0});
        vis[x][y] = true;

        while (!qlocal.empty()) {
            auto cur = qlocal.front(); qlocal.pop();
            int cx = cur.first.first;
            int cy = cur.first.second;
            int steps = cur.second;
            int t = bear[x][y];

            if (ong[cx][cy] > t + 1 && bear[cx][cy] > t + 1) {
                bear[cx][cy] = t + 1;
                q.push({cx, cy});
            }

            if (steps == S) continue;

            FOR(d,0,3) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];
                if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
                if (vis[nx][ny]) continue;
                if (forest[nx][ny] == 'T' || forest[nx][ny] == 'H') continue;
                if (ong[nx][ny] <= t) continue;

                vis[nx][ny] = true;
                qlocal.push({{nx, ny}, steps + 1});
            }
        }
    }

    return bear[tx][ty] != INF;
}

void solve() {
    cin >> n >> S;
    FOR(i,1,n) FOR(j,1,n) {
        cin >> forest[i][j];
        if (forest[i][j] == 'M') sx = i, sy = j;
        if (forest[i][j] == 'D') tx = i, ty = j;
    }

    FOR(i,1,n) FOR(j,1,n) {
        ong[i][j] = INF;
        vis[i][j] = false;
    }

    queue<pair<int,int>> s;
    FOR(i,1,n) FOR(j,1,n)
        if (forest[i][j] == 'H') {
            ong[i][j] = 0;
            vis[i][j] = true;
            s.push({i,j});
        }

    while (!s.empty()) {
        auto up = s.front(); s.pop();
        int x = up.first, y = up.second;
        FOR(d,0,3) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
            if (vis[nx][ny]) continue;
            if (forest[nx][ny] == 'T' || forest[nx][ny] == 'D') continue;
            ong[nx][ny] = ong[x][y] + 1;
            vis[nx][ny] = true;
            s.push({nx, ny});
        }
    }

    int low = 0, high = 2027, ans = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) ans = mid, low = mid + 1;
        else high = mid - 1;
    }

    cout << ans << '\n';
}

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

• Subtask 1: 35 / 100