#include<bits/stdc++.h>
using namespace std;
const int MAXN = 640000;
int n, s, fx, fy;
char g[MAXN][MAXN];
#define ff first
#define ss second
int dist[MAXN][MAXN], type[MAXN][MAXN];
int vis[MAXN][MAXN];
//type: 0 -- grass, 1 -- mecho, 2 -- hive, 3 -- tree;
int dx[] = {0, 1, 0, -1},
dy[] = {1, 0, -1, 0};
bool inbound(int x, int y){
return 1<=x && x <= n && 1 <= y && y <= n;
}
void print(){
for(int x = 1; x <= n; x++){
for(int y = 1; y <= n; y++)
cout << type[x][y];
cout << '\n';
}
cout << '\n';
}
queue<pair<int, int>> bq, mq;
void expandBee(){
if(bq.empty()) return;
int x = bq.front().ff, y = bq.front().ss;
int dini = dist[x][y];
while(!bq.empty()){
int x = bq.front().ff, y = bq.front().ss;
if(dist[x][y] > dini) break;
bq.pop();
for(int i = 0; i < 4; i++){
int nx = x+dx[i], ny = y+dy[i];
if(!inbound(nx, ny) || vis[nx][ny] > 1) continue;
if(type[nx][ny] < 2){
type[nx][ny] = 2;
dist[nx][ny] = dist[x][y]+1;
bq.push({nx, ny});
vis[nx][ny] = 2;
}
}
}
}
void expandMecho(){
while(!mq.empty()){
int x = mq.front().ff, y = mq.front().ss;
if(type[x][y] == 2) mq.pop();
else break;
}
if(mq.empty()) return;
int x = mq.front().ff, y = mq.front().ss;
int dini = dist[x][y];
while(!mq.empty()){
int x = mq.front().ff, y = mq.front().ss;
if(dist[x][y] >= dini+s) break;
mq.pop();
if(type[x][y] == 2) continue;
for(int i = 0; i < 4; i++){
int nx = x+dx[i], ny = y+dy[i];
if(!inbound(nx, ny) || vis[nx][ny] > 0) continue;
if(type[nx][ny] < 2 || type[nx][ny] == 4){
type[nx][ny] = 1;
dist[nx][ny] = dist[x][y]+1;
mq.push({nx, ny});
vis[nx][ny] = 1;
}
}
}
}
bool guess(int m){
while(mq.size()) mq.pop();
while(bq.size()) bq.pop();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
vis[i][j] = dist[i][j] = 0;
if(g[i][j] == 'G') type[i][j] = 0;
else if(g[i][j] == 'M') type[i][j] = 1, mq.push({i, j}), vis[i][j] = 1;
else if(g[i][j] == 'H') type[i][j] = 2, bq.push({i, j}), vis[i][j] = 2;
else if(g[i][j] == 'T') type[i][j] = 3;
else if(g[i][j] == 'D') type[i][j] = 4;
}
}
for(int i = 1; i <= m; i++) expandBee();
while(type[fx][fy] == 4){
expandMecho();
if(bq.empty()) return false;
if(type[fx][fy] == 1) return true;
expandBee();
}
return false;
}
int main(){
cin >> n >> s;
assert(n <= 60);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
cin >> g[i][j];
if(g[i][j] == 'D') fx = i, fy = j;
}
if(!guess(0)){
cout << -1;
return 0;
}
int l = 0, r = 640000;
while(l < r){
int m = (l+r+1)/2;
if(guess(m)) l = m;
else r = m-1;
}
cout << l << '\n';
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xd4): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
