#include <bits/stdc++.h>
using namespace std;
const int MAXN = 805;
const int INF = 1e9;
int n, k;
string a[MAXN];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int bees_time[MAXN][MAXN];
int sx=-1, sy=-1, tx=-1, ty=-1;
// precompute bees_time BFS from all H
void compute_bees_time(){
for(int i=0;i<n;i++) for(int j=0;j<n;j++) bees_time[i][j] = INF;
queue<pair<int,int>> 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});
}
if(a[i][j] == 'M'){ sx=i; sy=j; }
if(a[i][j] == 'D'){ tx=i; ty=j; }
}
}
while(!q.empty()){
auto cur = q.front(); q.pop();
int x = cur.first, y = cur.second;
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir], ny = y + dy[dir];
if(nx<0||nx>=n||ny<0||ny>=n) continue;
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[tx][ty] remains INF (bees don't enter D)
}
// can(t): Me waits t minutes, then simulate minute-by-minute. Within each minute we do up to k expansions using bitsets.
bool can(int t){
if(sx == -1 || tx == -1) return false;
if(bees_time[sx][sy] <= t) return false; // bees already at start while waiting
// precompute masks per row:
// passable_mid: cells Me can occupy/step into during minute (passable and not occupied by bees at start)
// passable_end: cells safe at end of minute (passable and bees won't be there at time+1)
static bitset<MAXN> passable_mid[MAXN], passable_end[MAXN], passable_all[MAXN];
for(int i=0;i<n;i++){
passable_all[i].reset();
passable_mid[i].reset();
passable_end[i].reset();
for(int j=0;j<n;j++){
bool pass = (a[i][j] == 'G' || a[i][j] == 'M' || a[i][j] == 'D');
if(pass) passable_all[i].set(j);
if(pass && bees_time[i][j] > t) passable_mid[i].set(j); // bees not there at start
if(pass && bees_time[i][j] > t + 1) passable_end[i].set(j); // safe at end of minute
}
}
// current set of positions (rows of bitsets)
static bitset<MAXN> curr[MAXN], visited[MAXN], tmp[MAXN];
for(int i=0;i<n;i++){ curr[i].reset(); visited[i].reset(); tmp[i].reset(); }
curr[sx].set(sy);
visited[sx].set(sy);
int time = t;
// if starting at D
if(sx == tx && sy == ty) return true;
while(true){
// BFS within one minute, multi-source, limited to k steps.
// visited_in_min stores all positions reached within <=k steps this minute.
for(int i=0;i<n;i++) visited[i] = curr[i]; // start visited = curr
bitset<MAXN> layer[MAXN];
for(int i=0;i<n;i++) layer[i] = curr[i];
// if any current position is D, success
if(curr[tx].any() && curr[tx].test(ty)) return true;
for(int step=0; step<k; ++step){
bool any = false;
// compute neighbours of layer (left/right/up/down) respecting passable_mid
// tmp = zero
for(int r=0;r<n;r++) tmp[r].reset();
for(int r=0;r<n;r++){
if(layer[r].none()) continue;
// left/right in same row
bitset<MAXN> lr;
lr = (layer[r] << 1) | (layer[r] >> 1);
lr &= passable_mid[r]; // cannot step into cells that bees occupy at start
tmp[r] |= lr;
// up
if(r > 0){
bitset<MAXN> up = layer[r];
up &= passable_mid[r-1];
tmp[r-1] |= up;
}
// down
if(r+1 < n){
bitset<MAXN> down = layer[r];
down &= passable_mid[r+1];
tmp[r+1] |= down;
}
}
// remove already visited
for(int r=0;r<n;r++){
tmp[r] &= (~visited[r]);
if(tmp[r].any()) any = true;
visited[r] |= tmp[r];
}
if(!any) break;
// check if reached D in this expansion
if(visited[tx].test(ty)) return true;
// prepare next layer
for(int r=0;r<n;r++) layer[r] = tmp[r];
}
// after up-to-k expansions, positions reachable within ≤k steps are in 'visited'
// we can only stand at those positions at end of minute if bees_time > time+1 (i.e., passable_end)
bool any_next = false;
for(int r=0;r<n;r++){
// select safe end positions
bitset<MAXN> safe = visited[r] & passable_end[r];
curr[r] = safe;
if(curr[r].any()) any_next = true;
}
if(!any_next) return false;
// check if any contains D
if(curr[tx].test(ty)) return true;
// advance minute
time++;
// update passable_mid and passable_end for new time
for(int i=0;i<n;i++){
// recompute passable_mid: passable and bees_time > time
// recompute passable_end: passable and bees_time > time+1
// (we could update incrementally, but recompute is O(n^2/word) per minute; acceptable)
passable_mid[i].reset();
passable_end[i].reset();
for(int j=0;j<n;j++){
bool pass = (a[i][j] == 'G' || a[i][j] == 'M' || a[i][j] == 'D');
if(pass && bees_time[i][j] > time) passable_mid[i].set(j);
if(pass && bees_time[i][j] > time + 1) passable_end[i].set(j);
}
}
// Also remove from curr any positions that become unsafe at start of next minute:
for(int r=0;r<n;r++){
curr[r] &= passable_mid[r];
}
// loop continues
}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if(!(cin >> n >> k)) return 0;
for(int i=0;i<n;i++) cin >> a[i];
compute_bees_time();
// tighten upper bound: if bees reach start at B, waiting >= B is impossible
int upper;
if(bees_time[sx][sy] == INF) upper = n * n;
else upper = min(n * n, bees_time[sx][sy] - 1);
int l = 0, r = upper, 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';
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
