Mecho

Solution

Binary Search on Waiting Time

\textbf{Feasibility check for a given $t$:}

1. Bee BFS: Multi-source BFS from all hives to compute $\text{bee\_time}[r][c]$ = the minute bees first reach $(r,c)$. Bees cannot enter the home cell $D$.

2. Mecho BFS: BFS from $M$. Cell $(r,c)$ is reachable at step-distance $d$ only if $\text{bee\_time}[r][c] > t + \lfloor d/S \rfloor$ (bees have not yet arrived when Mecho enters the cell).

3. If $D$ is reached, return true.

Complexity

• Time: $O(N^2 \log N)$ -- $O(\log N)$ binary search iterations, each with $O(N^2)$ BFS.

• Space: $O(N^2)$.

C++ Solution

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

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

    int N, S;
    cin >> N >> S;

    vector<string> grid(N);
    int mr, mc, dr, dc;
    vector<pair<int,int>> hives;

    for(int i = 0; i < N; i++){
        cin >> grid[i];
        for(int j = 0; j < N; j++){
            if(grid[i][j] == 'M'){ mr = i; mc = j; }
            if(grid[i][j] == 'D'){ dr = i; dc = j; }
            if(grid[i][j] == 'H') hives.push_back({i, j});
        }
    }

    // Bee BFS
    const int dx[] = {0, 0, 1, -1};
    const int dy[] = {1, -1, 0, 0};
    vector<vector<int>> beeTime(N, vector<int>(N, INT_MAX));
    queue<pair<int,int>> q;
    for(auto [r, c] : hives){
        beeTime[r][c] = 0;
        q.push({r, c});
    }
    while(!q.empty()){
        auto [r, c] = q.front(); q.pop();
        for(int d = 0; d < 4; d++){
            int nr = r + dx[d], nc = c + dy[d];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if(grid[nr][nc] == 'T' || grid[nr][nc] == 'D') continue;
            if(beeTime[nr][nc] <= beeTime[r][c] + 1) continue;
            beeTime[nr][nc] = beeTime[r][c] + 1;
            q.push({nr, nc});
        }
    }

    auto canEscape = [&](int t) -> bool {
        if(beeTime[mr][mc] <= t) return false;

        vector<vector<int>> dist(N, vector<int>(N, INT_MAX));
        dist[mr][mc] = 0;
        queue<pair<int,int>> bfs;
        bfs.push({mr, mc});

        while(!bfs.empty()){
            auto [r, c] = bfs.front(); bfs.pop();
            if(r == dr && c == dc) return true;
            for(int d = 0; d < 4; d++){
                int nr = r + dx[d], nc = c + dy[d];
                if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if(grid[nr][nc] == 'T') continue;
                if(dist[nr][nc] != INT_MAX) continue;
                int newDist = dist[r][c] + 1;
                int minute = t + newDist / S;
                if(nr != dr || nc != dc) // home is always safe
                    if(beeTime[nr][nc] <= minute) continue;
                dist[nr][nc] = newDist;
                bfs.push({nr, nc});
            }
        }
        return false;
    };

    int lo = 0, hi = N * N, ans = -1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(canEscape(mid)){ ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }

    cout << ans << "\n";
    return 0;
}

Notes

The bee BFS is computed once and reused across all binary-search iterations. In the Mecho BFS, the ``minute'' at which Mecho enters a cell is $t + \lfloor d/S \rfloor$, where $d$ is the number of individual steps taken. The home cell $D$ is excluded from bee spread, so Mecho can always enter it regardless of bee timing.