//#pragma GCC optimize ("O3") #include<iostream> #include<vector> #include<set> #include<map> #include<iomanip> #include <cassert> #include<algorithm> #include <cstring> #include<unordered_set> #include<queue> #include <array> #include<cmath> #include<unordered_map> #include<queue> #include <list> #include <bitset> using namespace std; #define int long long #define pii pair<int,int> #define LL long long //#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”) int INF = 1e18; vector<vector<int>>bee_vis; int n, s; int drix[4] = {0, 0, 1, -1}; int driy[4] = {1, -1, 0, 0}; vector<string>v; bool bee_valid(int x, int y){ //cout << x << y << endl; return (0 <= x && 0 <= y && x < n && y < n && (v[x][y] == 'G' || v[x][y] == 'M')); } bool bear_valid(int x, int y){ return (0 <= x && 0 <= y && x < n && y < n && (v[x][y] == 'G' || v[x][y] == 'D')); } vector<vector<int>> multi_bfs(){ vector<vector<int>>vis(n, vector<int>(n, INF)); queue<pii>q; for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ if(v[i][j] == 'H'){ q.push({i, j}); vis[i][j] = 0; } } } //exit(0); while(!q.empty()){ auto [x, y] = q.front(); for(int i = 0; i < 4; ++i){ if(!bee_valid(x + drix[i], y + driy[i])) continue; if(vis[x + drix[i]][y + driy[i]] == INF){ vis[x + drix[i]][y + driy[i]] = vis[x][y] + 1; q.push({x + drix[i], y + driy[i]}); } } q.pop(); } return vis; } bool bear_bfs(int st){ queue<pii>q; int hx, hy; vector<vector<int>>vis(n, vector<int>(n, INF)); for(int i = 0; i < n;++i){ for(int j = 0; j < n; ++j){ if(v[i][j] == 'M'){ vis[i][j] = 0; q.push({i, j}); } if(v[i][j] == 'D'){ hx = i; hy = j; } } } while(!q.empty()){ auto [x, y] = q.front(); q.pop(); for(int i = 0; i < 4; ++i){ int cx = x + drix[i]; int cy = y + driy[i]; if(!bear_valid(cx, cy)) continue; if(vis[cx][cy] != INF) continue; if((vis[x][y] + 1) / s + st < bee_vis[cx][cy]){ vis[cx][cy] = vis[x][y] + 1; q.push({cx, cy}); } } } return vis[hx][hy] != INF; } int32_t main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> s; v = vector<string>(n); for(int i = 0; i < n; ++i){ cin >> v[i]; } bee_vis = multi_bfs(); /* for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ cout << ((bee_vis[i][j] == INF) ? -1 : bee_vis[i][j]) << " "; }cout << endl; } */ if(!bear_bfs(0)){ cout << -1; return 0; } if(!bear_bfs(1)){ cout << 0; return 0; } int l = 1; int r = 1000001; while(l <= r){ int mid = (l + r) / 2; if(bear_bfs(mid)){ l = mid + 1; } else{ r = mid - 1; } } cout << r; }