#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define plpll pair<ll, pll>
#define pipii pair<int, pii>
#define plpii pair<ll, pii>
#define pipll pair<int, pll>
#define lll tuple<ll, ll, ll>
#define iii tuple<int, int, int>
#define lii tuple<ll, int, int>
#define lli tuple<ll, ll, int>
#define md 1000000007LL
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define lninf (ll)0xc0c0c0c0c0c0c0c0
#define ninf (int)0xc0c0c0c0
#define bruh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ss << ' ' <<
#ifdef wizard
#define usaco(x)
#else
#define usaco(x) ifstream cin(#x ".in"); ofstream cout(#x ".out");
#endif
template<class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
return in >> p.first >> p.second;
}
template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
return out << p.first << ' ' << p.second;
}
template<size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), istream&>::type
read_tuple(istream& in, tuple<Ts...>& t) { return in; }
template<size_t I = 0, typename... Ts>
typename enable_if<I < sizeof...(Ts), istream&>::type
read_tuple(istream& in, tuple<Ts...>& t) {
in >> get<I>(t);
return read_tuple<I + 1>(in, t);
}
template<typename... Ts>
istream& operator>>(istream& in, tuple<Ts...>& t) {
return read_tuple(in, t);
}
template<size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), void>::type
write_tuple(ostream& out, const tuple<Ts...>&) {}
template<size_t I = 0, typename... Ts>
typename enable_if<I < sizeof...(Ts), void>::type
write_tuple(ostream& out, const tuple<Ts...>& t) {
if (I) out << ' ';
out << get<I>(t);
write_tuple<I + 1>(out, t);
}
template<typename... Ts>
ostream& operator<<(ostream& out, const tuple<Ts...>& t) {
write_tuple(out, t);
return out;
}
template<typename T>
istream& operator>>(istream& in, vector<T>& v) {
for (auto& x : v) in >> x;
return in;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
for (size_t i = 0; i < v.size(); ++i)
out << (i ? " " : "") << v[i];
return out;
}
const pii dd[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n, s, bee[800][800], dist[800][800], l, r = 640000, mid, ans = -1;
char t[800][800];
queue<pii> q;
pii st, ed;
int main() {
bruh;
cin >> n >> s;
memset(bee, 0x3f, sizeof bee);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
cin >> t[i][j];
if (t[i][j] == 'H') q.push({i, j}), bee[i][j] = 0;
else if (t[i][j] == 'M') st = {i, j};
else if (t[i][j] == 'D') ed = {i, j};
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (auto [dx, dy]: dd) {
auto xx = x + dx, yy = y + dy;
if (xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
if (t[xx][yy] == 'T') continue;
if (bee[xx][yy] == inf) bee[xx][yy] = bee[x][y] + 1, q.push({xx, yy});
}
}
while (l <= r) {
mid = (l + r) >> 1;
memset(dist, 0x3f, sizeof dist); dist[st.first][st.second] = 0;
if (mid >= bee[st.first][st.second]) { r = mid - 1; continue; }
q.push(st);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (auto [dx, dy]: dd) {
auto xx = x + dx, yy = y + dy;
if (xx < 0 || yy < 0 || xx >= n || yy >= n) continue;
if (t[xx][yy] == 'T') continue;
if ((dist[x][y] + 1)/s + mid >= bee[xx][yy]) continue;
if (dist[xx][yy] == inf) dist[xx][yy] = dist[x][y] + 1, q.push({xx, yy});
}
}
if (dist[ed.first][ed.second] != inf) ans = mid, l = mid + 1;
else r = mid - 1;
}
cout << ans;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
