// 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;
if((dist[0][_x][_y] + S - 1)/S >= dist[1][_x][_y])continue;
int dif = dist[1][_x][_y] == 2e9 ? min_possible : dist[1][_x][_y] - (dist[0][_x][_y] + S - 1)/S;
// db(x , y , _x , _y,dif );
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
*/
Compilation message
mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:212:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:213:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
213 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
4456 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Incorrect |
44 ms |
33836 KB |
Output isn't correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 13 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 16 |
Incorrect |
1 ms |
4560 KB |
Output isn't correct |
| 17 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 18 |
Incorrect |
1 ms |
4524 KB |
Output isn't correct |
| 19 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 20 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 21 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 22 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 23 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 24 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 25 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 26 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 27 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 28 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 29 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 30 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 31 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 32 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 33 |
Incorrect |
5 ms |
6744 KB |
Output isn't correct |
| 34 |
Incorrect |
7 ms |
9052 KB |
Output isn't correct |
| 35 |
Incorrect |
10 ms |
13404 KB |
Output isn't correct |
| 36 |
Incorrect |
6 ms |
9048 KB |
Output isn't correct |
| 37 |
Incorrect |
8 ms |
11868 KB |
Output isn't correct |
| 38 |
Incorrect |
13 ms |
17500 KB |
Output isn't correct |
| 39 |
Incorrect |
6 ms |
9032 KB |
Output isn't correct |
| 40 |
Incorrect |
9 ms |
12628 KB |
Output isn't correct |
| 41 |
Incorrect |
21 ms |
19972 KB |
Output isn't correct |
| 42 |
Incorrect |
8 ms |
9308 KB |
Output isn't correct |
| 43 |
Incorrect |
11 ms |
13496 KB |
Output isn't correct |
| 44 |
Incorrect |
27 ms |
22620 KB |
Output isn't correct |
| 45 |
Incorrect |
12 ms |
9048 KB |
Output isn't correct |
| 46 |
Incorrect |
12 ms |
14680 KB |
Output isn't correct |
| 47 |
Incorrect |
22 ms |
25684 KB |
Output isn't correct |
| 48 |
Incorrect |
11 ms |
9308 KB |
Output isn't correct |
| 49 |
Incorrect |
15 ms |
15820 KB |
Output isn't correct |
| 50 |
Incorrect |
30 ms |
28752 KB |
Output isn't correct |
| 51 |
Incorrect |
12 ms |
9304 KB |
Output isn't correct |
| 52 |
Incorrect |
21 ms |
16988 KB |
Output isn't correct |
| 53 |
Incorrect |
33 ms |
32336 KB |
Output isn't correct |
| 54 |
Incorrect |
14 ms |
9556 KB |
Output isn't correct |
| 55 |
Incorrect |
21 ms |
18256 KB |
Output isn't correct |
| 56 |
Incorrect |
37 ms |
36180 KB |
Output isn't correct |
| 57 |
Incorrect |
22 ms |
9560 KB |
Output isn't correct |
| 58 |
Incorrect |
23 ms |
19800 KB |
Output isn't correct |
| 59 |
Incorrect |
45 ms |
40280 KB |
Output isn't correct |
| 60 |
Incorrect |
19 ms |
10076 KB |
Output isn't correct |
| 61 |
Incorrect |
27 ms |
21364 KB |
Output isn't correct |
| 62 |
Incorrect |
51 ms |
44628 KB |
Output isn't correct |
| 63 |
Incorrect |
27 ms |
9816 KB |
Output isn't correct |
| 64 |
Incorrect |
37 ms |
10064 KB |
Output isn't correct |
| 65 |
Incorrect |
31 ms |
10236 KB |
Output isn't correct |
| 66 |
Incorrect |
27 ms |
9752 KB |
Output isn't correct |
| 67 |
Correct |
27 ms |
9808 KB |
Output is correct |
| 68 |
Incorrect |
31 ms |
9804 KB |
Output isn't correct |
| 69 |
Incorrect |
33 ms |
10324 KB |
Output isn't correct |
| 70 |
Incorrect |
30 ms |
9808 KB |
Output isn't correct |
| 71 |
Incorrect |
35 ms |
9812 KB |
Output isn't correct |
| 72 |
Incorrect |
33 ms |
10076 KB |
Output isn't correct |
| 73 |
Correct |
35 ms |
18400 KB |
Output is correct |
| 74 |
Incorrect |
52 ms |
40280 KB |
Output isn't correct |
| 75 |
Incorrect |
35 ms |
17788 KB |
Output isn't correct |
| 76 |
Incorrect |
39 ms |
18516 KB |
Output isn't correct |
| 77 |
Incorrect |
36 ms |
19280 KB |
Output isn't correct |
| 78 |
Correct |
45 ms |
28240 KB |
Output is correct |
| 79 |
Incorrect |
53 ms |
44112 KB |
Output isn't correct |
| 80 |
Incorrect |
40 ms |
25352 KB |
Output isn't correct |
| 81 |
Incorrect |
42 ms |
26140 KB |
Output isn't correct |
| 82 |
Incorrect |
56 ms |
29524 KB |
Output isn't correct |
| 83 |
Incorrect |
37 ms |
21332 KB |
Output isn't correct |
| 84 |
Incorrect |
50 ms |
33876 KB |
Output isn't correct |
| 85 |
Incorrect |
39 ms |
20564 KB |
Output isn't correct |
| 86 |
Incorrect |
42 ms |
21600 KB |
Output isn't correct |
| 87 |
Incorrect |
39 ms |
21596 KB |
Output isn't correct |
| 88 |
Incorrect |
38 ms |
19960 KB |
Output isn't correct |
| 89 |
Incorrect |
49 ms |
29808 KB |
Output isn't correct |
| 90 |
Incorrect |
38 ms |
20540 KB |
Output isn't correct |
| 91 |
Incorrect |
52 ms |
22252 KB |
Output isn't correct |
| 92 |
Incorrect |
35 ms |
19936 KB |
Output isn't correct |
