제출 #1275090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275090		lmduc270410	Mecho (IOI09_mecho)	C++20	53 / 100	404 ms	7652 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 800 + 5;
const int INF = 1e9;

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

int n, k;
string a[N];

// bees_time[x][y] = phút khi ong lần đầu chiếm ô (hive = 0). INF nếu ong không chiếm.
int bees_time[N][N];

bool inside(int x, int y){ return x>=0 && x<n && y>=0 && y<n; }

void compute_bees_time(){
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) bees_time[i][j] = INF;
    queue<pii> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j] == 'H'){
                bees_time[i][j] = 0;
                q.push({i,j});
            }
        }
    }
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int x = cur.fi, y = cur.se;
        for(int dir=0; dir<4; dir++){
            int nx = x + dx[dir], ny = y + dy[dir];
            if(!inside(nx, ny)) continue;
            // ong chỉ lan tới ô G hoặc M (M treated like G)
            if(a[nx][ny] != 'G' && a[nx][ny] != 'M') continue;
            if(bees_time[nx][ny] == INF){
                bees_time[nx][ny] = bees_time[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    // bees_time at 'D' remains INF (ong không vào D)
}

// Kiểm tra với thời gian chờ t (Mecho đợi t phút trước khi bắt đầu di chuyển)
// Trả true nếu Me có thể tới 'D' sau khi đợi t phút (và tránh ong).
bool can(int t){
    // tìm vị trí bắt đầu (M) và đích (D)
    int sx=-1, sy=-1, tx=-1, ty=-1;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){
        if(a[i][j] == 'M'){ sx = i; sy = j; }
        if(a[i][j] == 'D'){ tx = i; ty = j; }
    }
    if(sx==-1 || tx==-1) return false;
    // nếu ong đã tới chỗ M trước hoặc đúng lúc Me còn chờ => fail
    if(bees_time[sx][sy] <= t) return false;

    // seen: đánh dấu ô Me đã từng đứng ở cuối một phút (không cần lặp lại)
    static bool seen[N][N];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) seen[i][j] = false;

    queue<pii> curr; // các ô Me có thể đứng vào đầu phút (đầu tiên là sau t phút chờ)
    curr.push({sx, sy});
    seen[sx][sy] = true;

    int time = t; // hiện tại là phút đã trôi (ong đã chiếm bees_time <= time)

    while(!curr.empty()){
        // BFS multi-source trong 1 phút với depth limit = k
        queue<pair<pii,int>> bfsq;
        // inbfs để tránh push trùng trong BFS nội bộ
        static bool inbfs[N][N];
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) inbfs[i][j] = false;

        int curr_sz = curr.size();
        // push tất cả vị trí hiện tại (đầu phút) vào bfsq như depth=0
        while(curr_sz--){
            auto p = curr.front(); curr.pop();
            int x = p.fi, y = p.se;
            // Nếu đang ở D -> success
            if(x == tx && y == ty) return true;
            // nếu ong đã có ở ô này tại thời điểm bắt đầu phút thì bỏ (an toàn check, nhưng initial check tránh trường hợp)
            if(bees_time[x][y] <= time) continue;
            bfsq.push({{x,y}, 0});
            inbfs[x][y] = true;
        }

        queue<pii> next; // vị trí Me có thể đứng ở cuối phút (time+1)
        while(!bfsq.empty()){
            auto cur = bfsq.front(); bfsq.pop();
            int x = cur.first.first, y = cur.first.second, d = cur.second;
            // Nếu chạm D trong nội bộ phút -> success
            if(x == tx && y == ty) return true;
            // Me có thể đứng ở ô này vào cuối phút nếu ong chưa tới ô đó ở phút time+1
            if(bees_time[x][y] > time + 1 && !seen[x][y]){
                next.push({x,y});
                seen[x][y] = true;
            }
            if(d == k) continue;
            for(int dir=0; dir<4; dir++){
                int nx = x + dx[dir], ny = y + dy[dir];
                if(!inside(nx, ny)) continue;
                if(inbfs[nx][ny]) continue;
                // Me có thể đi qua G hoặc D or M(start)
                if(!(a[nx][ny] == 'G' || a[nx][ny] == 'D' || a[nx][ny] == 'M')) continue;
                // không thể đi vào ô mà ong đã chiếm trước khi bắt đầu phút này
                if(bees_time[nx][ny] <= time) continue;
                inbfs[nx][ny] = true;
                bfsq.push({{nx, ny}, d+1});
            }
        }

        // tiến sang phút kế
        time++;
        // chuẩn bị vòng lặp với các vị trí có thể đứng vào đầu phút mới
        curr = move(next);
    }
    return false;
}

void solve(){
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];

    compute_bees_time();

    int l = 0, r = 2 * n, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(can(mid)){
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    cout<<ans<<"\n";
}

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

• Subtask 1: 53 / 100