// to live is to die
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n) \
for (int i = 0; i <= n; i++) \
{ \
a[i] = 0; \
}
#define clearMat(a, n, m, d) \
for (int i = 0; i <= n; i++) \
{ \
for (int j = 0; j <= m; j++) \
a[i][j] = d; \
}
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)
#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void __print(int x)
{
cerr << x;
}
void __print(long x)
{
cerr << x;
}
void __print(long long x)
{
cerr << x;
}
void __print(unsigned x)
{
cerr << x;
}
void __print(unsigned long x)
{
cerr << x;
}
void __print(unsigned long long x)
{
cerr << x;
}
void __print(float x)
{
cerr << x;
}
void __print(double x)
{
cerr << x;
}
void __print(long double x)
{
cerr << x;
}
void __print(char x)
{
cerr << '\'' << x << '\'';
}
void __print(const char *x)
{
cerr << '\"' << x << '\"';
}
void __print(const string &x)
{
cerr << '\"' << x << '\"';
}
void __print(bool x)
{
cerr << (x ? "true" : "false");
}
template<typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template<typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print()
{
cerr << "]\n";
}
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v)) cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define db(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define db(x...)
#endif
// order_of_key(k): # of elements less than k (which is the index of x = k)
// find_by_order(k); iterator of the k-th element
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
bool ckmin(T &a, const T &b)
{
return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b)
{
return a < b ? a = b, 1 : 0;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &a)
{
for (auto &x : a)
in >> x;
return in;
};
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a)
{
for (auto &x : a)
out << x << ' ';
return out;
};
// priority_queue<data type , the container that would hold the values , greater<pair<int,int>>>
// greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m
char to_char(int num)
{
return (char)(num + '0');
}
ll const MAX = 1e18 + 1;
ll const oo = 1e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 998244353;
ll const SIZE = 2e5 + 900;
const int LOG = 20;
template <typename T, typename T2>
ll add(T X, T2 Y)
{
X += Y;
if (X >= MOD)
{
X -= MOD;
}
return X;
}
template <typename T, typename T2>
ll sub(T X , T2 Y)
{
X -= Y;
if(X < 0) X += MOD;
return X;
}
template <typename T, typename T2>
T mult(T X, T2 Y)
{
return X * Y % MOD;
}
void setIO(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
// x & (-x) give me the minBit of x
// x & (x - 1) turns off rightmost bit
int dist[3][1003][1003];
bool vis[1003][1003];
int dx[4] = {0 , 0 , 1 , -1};
int dy[4] = {1 , -1 , 0 , 0};
void solve()
{
//M , G : YES
//T , H : NO;
// he can make S steps by minute
//every minute each bee hive spread to its 4 adjacent cells
int N , S;
cin >> N >> S;
vector<string>mat(N);
vpi hives;
int Dx{} , Dy{};
int mx{} , my{};
rep(i , N)
{
cin >> mat[i];
rep(j , N)
{
dist[0][i][j] = dist[1][i][j] = 2e9;
if(mat[i][j] == 'H')
{
hives.PB({i , j});
}
if(mat[i][j] == 'D')
{
Dx = i ; Dy = j;
}
if(mat[i][j] == 'M')
{
mx = i ; my = j;
}
}
}
auto valid = [&](int x , int y)
{
return x >= 0 && x < N && y < N && y >= 0;
};
function<void(vpi , bool)> BFS = [&](vpi sources , bool ty)
{
queue<pi>Q;
for(auto [x , y] : sources)
{
Q.push({x, y});
dist[ty][x][y] = 0;
}
while(!Q.empty())
{
pi cur = Q.front();
Q.pop();
int x = cur.F;
int y = cur.S;
for(int i = 0 ; i < 4 ; i++)
{
int _x = x + dx[i];
int _y = y + dy[i];
if(!valid(_x , _y))continue;
if(ty == 0)
{
//i am M
if(mat[_x][_y] == 'H' || mat[_x][_y] == 'T')continue;
}
if(mat[_x][_y] == 'D' && ty == 1)
{
//a bee
continue;
}
if(dist[ty][_x][_y] > dist[ty][x][y] + 1)
{
dist[ty][_x][_y] = dist[ty][x][y] + 1;
Q.push({_x , _y});
}
}
}
};
BFS(vpi{{mx , my}} , 0);
BFS(hives , 1);
int answer = -1;
function<void(int , int , int)> DFS = [&](int x , int y , int min_possible)->void
{
vis[x][y] = 1;
for(int i = 0 ;i < 4 ; i++)
{
int _x = x + dx[i];
int _y = y + dy[i];
if(!valid(_x , _y) || mat[_x][_y] == 'T' || mat[_x][_y] == 'H' || vis[_x][_y])continue;
int Mm = (dist[0][_x][_y] + S - 1)/S;// ceil or floor?
int Ms = dist[0][_x][_y];
int Hm = dist[1][_x][_y];
int Hs = dist[1][_x][_y] * S;
int dif{};
if(Hs < Ms)
{
continue;//cannot go there
}
if(Hs == Ms)
{
dif = 0;
}else // Hs > Ms , how much we can stay eating
{
dif = Hm - Mm;
}
if(_x == Dx && _y == Dy)
{
answer = max(answer , min(dif , min_possible));
// db(x , y , dif , answer);
}
DFS(_x , _y , min(min_possible , dif));
}
};
DFS(mx, my , 2e9);
cout << answer << "\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// setIO("atlarge");
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
/* stuff you should look for
* WRITE STUFF DOWN, ON PAPER
* BFS THEN DFS
* int overflow, array bounds
* special cases (n=1?)
* do sm th instead of nothing and stay organized
* DON'T GET STUCK ON ONE APPROACH
* (STUCK?)******** Try to simplify the problem(keeping in mind the main problem), ():
* 1- problem to subProblem
* 2- from simple to complex: start with a special
* problem and then try to update the solution for general case
* -(constraints - > solve it with none , one,two ... of them till you reach the given problem
-(no constraints - > try to give it some)
-how a special case may be incremented
* 3-Simplification by Assumptions
* REVERSE PROBLEM
* PROBLEM ABSTRACTION
* SMALL O BSERVATIONS MIGHT HELP ALOT
* WATCH OUT FOR TIME
* RETHINK YOUR IDEA,BETTER IDEA, APPROACH?
* CORRECT IDEA, NEED MORE OBSERVATIONS
* CORRECT APPROACH, WRONG IDEA
* WRONG APPROACH
* THINK CONCRETE THEN SYMBOL,
* having the solution for the first m state , can we solve it for m + 1 ?
* in many cases incremental thinking needs data sorting
*/
