#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math,unsafe-math-optimizations")
#define int long long
#define f first
#define s second
#define pii pair <int, int>
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define emb emplace_back
using namespace std;
const int inf = 1e6;
const int mod = 998244353;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
bool can(int k, int n, int sx, int sy, int ex, int ey, vector <vector <int>> &bee, vector <vector <char>> &a, int mid) {
if (bee[sx][sy] <= mid) return false;
queue <pii> q; q.emplace(sx, sy);
vector <vector <int>> bear(n, vector <int> (n, inf));
vector <vector <bool>> home(n, vector <bool> (n));
for (int i = 0; i < 4; i++) {
int eex = ex + dx[i], eey = ey + dy[i];
if (eex < 0 || eex >= n || eey < 0 || eey >= n) continue;
home[eex][eey] = true;
}
bear[sx][sy] = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
int dist = (bear[x][y]+1) / k;
if (nx < 0 || nx >= n || ny < 0 || ny >= n || bear[nx][ny] != inf || dist + mid >= bee[nx][ny] || a[nx][ny] == 'T') continue;
if (home[nx][ny]) return true;
bear[nx][ny] = bear[x][y]+1;
q.emplace(nx, ny);
}
}
return false;
}
int32_t main(){
iShowSpeed;
int n, k; cin >> n >> k;
vector <vector <char>> a(n, vector <char> (n));
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
vector <vector <int>> bee(n, vector <int> (n, inf)), bear(n, vector <int> (n, inf));
queue <pii> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'H') bee[i][j] = 0, q.emplace(i, j);
}
}
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || bee[nx][ny] <= bee[x][y] + 1 || a[nx][ny] == 'T') continue;
if(bee[nx][ny] > bee[x][y] + 1) bee[nx][ny] = bee[x][y] + 1, q.emplace(nx, ny);;
}
}
int sx, sy, ex, ey;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 'M') sx = i, sy = j;
if (a[i][j] == 'D') ex = i, ey = j;
}
}
int ans = -1;
int l = 0, r = n * n;
while (l <= r) {
int mid = (l + r) / 2;
if (can(k, n, sx, sy, ex, ey, bee, a, mid)) {
l = mid + 1;
ans = max(ans, mid);
}
else r = mid - 1;
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |