// 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(ty == 1)
{
//a bee
if(mat[_x][_y] == 'D' || mat[_x][_y] == 'T')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
*/
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 |
4440 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
4444 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
4556 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 7 |
Incorrect |
44 ms |
33996 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
4696 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
4440 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
4444 KB |
Output isn't 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 |
0 ms |
4444 KB |
Output isn't correct |
| 16 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 17 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 18 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 19 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 20 |
Correct |
1 ms |
4444 KB |
Output is 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 |
Correct |
1 ms |
4500 KB |
Output is correct |
| 25 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 26 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 27 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 28 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 29 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 30 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 31 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 32 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 33 |
Incorrect |
5 ms |
10076 KB |
Output isn't correct |
| 34 |
Incorrect |
5 ms |
10076 KB |
Output isn't correct |
| 35 |
Incorrect |
10 ms |
13404 KB |
Output isn't correct |
| 36 |
Incorrect |
10 ms |
13404 KB |
Output isn't correct |
| 37 |
Incorrect |
8 ms |
13148 KB |
Output isn't correct |
| 38 |
Incorrect |
11 ms |
17556 KB |
Output isn't correct |
| 39 |
Incorrect |
12 ms |
14428 KB |
Output isn't correct |
| 40 |
Correct |
10 ms |
14424 KB |
Output is correct |
| 41 |
Incorrect |
14 ms |
19804 KB |
Output isn't correct |
| 42 |
Incorrect |
10 ms |
15856 KB |
Output isn't correct |
| 43 |
Incorrect |
16 ms |
15708 KB |
Output isn't correct |
| 44 |
Incorrect |
22 ms |
22576 KB |
Output isn't correct |
| 45 |
Incorrect |
12 ms |
17500 KB |
Output isn't correct |
| 46 |
Incorrect |
14 ms |
17192 KB |
Output isn't correct |
| 47 |
Incorrect |
20 ms |
25436 KB |
Output isn't correct |
| 48 |
Incorrect |
13 ms |
19180 KB |
Output isn't correct |
| 49 |
Correct |
14 ms |
19036 KB |
Output is correct |
| 50 |
Incorrect |
28 ms |
28508 KB |
Output isn't correct |
| 51 |
Incorrect |
16 ms |
20828 KB |
Output isn't correct |
| 52 |
Incorrect |
22 ms |
20572 KB |
Output isn't correct |
| 53 |
Incorrect |
29 ms |
32088 KB |
Output isn't correct |
| 54 |
Incorrect |
20 ms |
22872 KB |
Output isn't correct |
| 55 |
Correct |
19 ms |
22616 KB |
Output is correct |
| 56 |
Incorrect |
33 ms |
35804 KB |
Output isn't correct |
| 57 |
Incorrect |
21 ms |
24924 KB |
Output isn't correct |
| 58 |
Correct |
24 ms |
24668 KB |
Output is correct |
| 59 |
Incorrect |
39 ms |
39928 KB |
Output isn't correct |
| 60 |
Incorrect |
24 ms |
26964 KB |
Output isn't correct |
| 61 |
Incorrect |
30 ms |
26964 KB |
Output isn't correct |
| 62 |
Incorrect |
49 ms |
44184 KB |
Output isn't correct |
| 63 |
Incorrect |
36 ms |
9812 KB |
Output isn't correct |
| 64 |
Correct |
38 ms |
9812 KB |
Output is correct |
| 65 |
Incorrect |
39 ms |
9880 KB |
Output isn't correct |
| 66 |
Incorrect |
36 ms |
9836 KB |
Output isn't correct |
| 67 |
Correct |
33 ms |
9564 KB |
Output is correct |
| 68 |
Incorrect |
34 ms |
9820 KB |
Output isn't correct |
| 69 |
Correct |
34 ms |
9808 KB |
Output is correct |
| 70 |
Incorrect |
33 ms |
9812 KB |
Output isn't correct |
| 71 |
Correct |
32 ms |
9812 KB |
Output is correct |
| 72 |
Incorrect |
41 ms |
9808 KB |
Output isn't correct |
| 73 |
Incorrect |
37 ms |
17748 KB |
Output isn't correct |
| 74 |
Incorrect |
53 ms |
40796 KB |
Output isn't correct |
| 75 |
Incorrect |
35 ms |
17748 KB |
Output isn't correct |
| 76 |
Incorrect |
34 ms |
18000 KB |
Output isn't correct |
| 77 |
Incorrect |
36 ms |
18772 KB |
Output isn't correct |
| 78 |
Correct |
38 ms |
27956 KB |
Output is correct |
| 79 |
Incorrect |
55 ms |
46420 KB |
Output isn't correct |
| 80 |
Incorrect |
51 ms |
25264 KB |
Output isn't correct |
| 81 |
Incorrect |
41 ms |
25876 KB |
Output isn't correct |
| 82 |
Incorrect |
41 ms |
29008 KB |
Output isn't correct |
| 83 |
Incorrect |
37 ms |
20888 KB |
Output isn't correct |
| 84 |
Incorrect |
52 ms |
37720 KB |
Output isn't correct |
| 85 |
Incorrect |
35 ms |
20304 KB |
Output isn't correct |
| 86 |
Incorrect |
35 ms |
21124 KB |
Output isn't correct |
| 87 |
Incorrect |
36 ms |
21072 KB |
Output isn't correct |
| 88 |
Correct |
37 ms |
19504 KB |
Output is correct |
| 89 |
Incorrect |
48 ms |
32156 KB |
Output isn't correct |
| 90 |
Incorrect |
35 ms |
20308 KB |
Output isn't correct |
| 91 |
Incorrect |
40 ms |
20052 KB |
Output isn't correct |
| 92 |
Incorrect |
35 ms |
19268 KB |
Output isn't correct |
