// 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};
int mn[1003][1003];
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;
mn[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_bee = [&](int x , int y)
{
return x >= 0 && x < N && y < N && y >= 0 && mat[x][y] != 'T' && mat[x][y] != 'D' && dist[1][x][y] == 2e9;
};
auto valid_M = [&](int x , int y)
{
return x >= 0 && x < N && y < N && y >= 0 && mat[x][y] != 'T' && mat[x][y] != 'H' && dist[0][x][y] == -1;
};
function<void(vpi)> multisource_BFS = [&](vpi sources)
{
queue<pi>Q;
for(auto [x , y] : sources)
{
Q.push({x, y});
dist[1][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_bee(_x , _y))continue;
dist[1][_x][_y] = dist[1][x][y] + 1;
Q.push({_x , _y});
}
}
};
auto can_go = [&](int x, int y)->bool
{
return x/S < y;
};
function<bool(int)> is_good = [&](int mid)->bool
{
//mid : minutes he can spend eating honey
if(dist[1][mx][my] <= mid)return 0;
memset(dist[0] , -1 , sizeof dist[0]);
dist[0][mx][my] = 0;
queue<pi> Q;
Q.push({mx , my});
while(!Q.empty())
{
pi cur = Q.front();
Q.pop();
int x = cur.F;
int y = cur.S;
rep(i , 4)
{
int _x = x + dx[i];
int _y = y + dy[i];
if(!valid_M(_x , _y))continue;
if(_x == Dx && _y == Dy)return true;
if(can_go(dist[0][x][y] + 1 , dist[1][_x][_y] - mid))
{
dist[0][_x][_y] = dist[0][x][y] + 1;
Q.push({_x , _y});
}
}
}
return dist[0][Dx][Dy] != -1;
};
multisource_BFS(hives);
int L = 0 , R = 1e6;
int answer = -1;
while(L <= R)
{
int mid = (L + R)/2;
if(is_good(mid))
{
answer = mid;
L = mid + 1;
}else{
R = mid - 1;
}
}
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 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6608 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
59 ms |
13756 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 13 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 14 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 15 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 19 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 20 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 21 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 22 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 23 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 24 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 25 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 26 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 27 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 28 |
Correct |
1 ms |
8792 KB |
Output is correct |
| 29 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 30 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 31 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 32 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 33 |
Correct |
3 ms |
8792 KB |
Output is correct |
| 34 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 35 |
Correct |
14 ms |
8980 KB |
Output is correct |
| 36 |
Correct |
4 ms |
8796 KB |
Output is correct |
| 37 |
Correct |
3 ms |
8796 KB |
Output is correct |
| 38 |
Correct |
18 ms |
9024 KB |
Output is correct |
| 39 |
Correct |
4 ms |
11096 KB |
Output is correct |
| 40 |
Correct |
4 ms |
11100 KB |
Output is correct |
| 41 |
Correct |
25 ms |
11100 KB |
Output is correct |
| 42 |
Correct |
5 ms |
11100 KB |
Output is correct |
| 43 |
Correct |
5 ms |
11100 KB |
Output is correct |
| 44 |
Correct |
30 ms |
11100 KB |
Output is correct |
| 45 |
Correct |
6 ms |
11100 KB |
Output is correct |
| 46 |
Correct |
5 ms |
11100 KB |
Output is correct |
| 47 |
Correct |
36 ms |
11232 KB |
Output is correct |
| 48 |
Correct |
6 ms |
13148 KB |
Output is correct |
| 49 |
Correct |
6 ms |
13148 KB |
Output is correct |
| 50 |
Correct |
52 ms |
13148 KB |
Output is correct |
| 51 |
Correct |
7 ms |
13404 KB |
Output is correct |
| 52 |
Correct |
6 ms |
13292 KB |
Output is correct |
| 53 |
Correct |
51 ms |
13404 KB |
Output is correct |
| 54 |
Correct |
7 ms |
13400 KB |
Output is correct |
| 55 |
Correct |
7 ms |
13404 KB |
Output is correct |
| 56 |
Correct |
59 ms |
13488 KB |
Output is correct |
| 57 |
Correct |
9 ms |
13400 KB |
Output is correct |
| 58 |
Correct |
8 ms |
13404 KB |
Output is correct |
| 59 |
Correct |
66 ms |
13544 KB |
Output is correct |
| 60 |
Correct |
8 ms |
13400 KB |
Output is correct |
| 61 |
Correct |
9 ms |
13404 KB |
Output is correct |
| 62 |
Correct |
76 ms |
13632 KB |
Output is correct |
| 63 |
Correct |
80 ms |
13404 KB |
Output is correct |
| 64 |
Correct |
127 ms |
13400 KB |
Output is correct |
| 65 |
Correct |
115 ms |
13400 KB |
Output is correct |
| 66 |
Correct |
101 ms |
13400 KB |
Output is correct |
| 67 |
Correct |
80 ms |
13624 KB |
Output is correct |
| 68 |
Correct |
35 ms |
13660 KB |
Output is correct |
| 69 |
Correct |
34 ms |
13656 KB |
Output is correct |
| 70 |
Correct |
30 ms |
13656 KB |
Output is correct |
| 71 |
Correct |
25 ms |
13660 KB |
Output is correct |
| 72 |
Correct |
21 ms |
13660 KB |
Output is correct |
| 73 |
Correct |
25 ms |
13916 KB |
Output is correct |
| 74 |
Correct |
52 ms |
13916 KB |
Output is correct |
| 75 |
Correct |
45 ms |
13912 KB |
Output is correct |
| 76 |
Correct |
40 ms |
13912 KB |
Output is correct |
| 77 |
Correct |
43 ms |
13916 KB |
Output is correct |
| 78 |
Correct |
46 ms |
13912 KB |
Output is correct |
| 79 |
Correct |
36 ms |
13916 KB |
Output is correct |
| 80 |
Correct |
47 ms |
13912 KB |
Output is correct |
| 81 |
Correct |
45 ms |
13916 KB |
Output is correct |
| 82 |
Correct |
34 ms |
13916 KB |
Output is correct |
| 83 |
Correct |
52 ms |
13660 KB |
Output is correct |
| 84 |
Correct |
46 ms |
13660 KB |
Output is correct |
| 85 |
Correct |
47 ms |
13864 KB |
Output is correct |
| 86 |
Correct |
52 ms |
13656 KB |
Output is correct |
| 87 |
Correct |
48 ms |
13660 KB |
Output is correct |
| 88 |
Correct |
55 ms |
13660 KB |
Output is correct |
| 89 |
Correct |
55 ms |
13656 KB |
Output is correct |
| 90 |
Correct |
56 ms |
13796 KB |
Output is correct |
| 91 |
Correct |
54 ms |
13656 KB |
Output is correct |
| 92 |
Correct |
54 ms |
13660 KB |
Output is correct |
