| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1314698 | menkh | Mecho (IOI09_mecho) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define MAX 805
const int INF = 1000000000 + 10;
char forest[MAX][MAX];
int bear[MAX][MAX];
int ong[MAX][MAX];
bool vis[MAX][MAX];
int n, S;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int x1, y1, x2, y2;
bool check(int k) {
if (k >= ong[x1][y1]) return false;
FOR(i,1,n) FOR(j,1,n) bear[i][j] = INF;
queue<pair<int,int>> q;
bear[x1][y1] = k;
q.push({x1, y1});
while (!q.empty()) {
auto it = q.front(); q.pop();
int x = it.first, y = it.second;
FOR(i,1,n) FOR(j,1,n) vis[i][j] = false;
queue<pair<pair<int,int>,int>> qlocal;
qlocal.push({{x, y}, 0});
vis[x][y] = true;
while (!qlocal.empty()) {
auto cur = qlocal.front(); qlocal.pop();
int cx = cur.first.first;
int cy = cur.first.second;
int steps = cur.second;
int t = bear[x][y];
if (ong[cx][cy] > t + 1 && bear[cx][cy] > t + 1) {
bear[cx][cy] = t + 1;
q.push({cx, cy});
}
if (steps == S) continue;
FOR(d,0,3) {
int nx = cx + dx[d];
int ny = cy + dy[d];
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
if (vis[nx][ny]) continue;
if (forest[nx][ny] == 'T' || forest[nx][ny] == 'H') continue;
if (ong[nx][ny] <= t) continue;
vis[nx][ny] = true;
qlocal.push({{nx, ny}, steps + 1});
}
}
}
return bear[x2][y2] != INF;
}
void solve() {
cin >> n >> S;
FOR(i,1,n) FOR(j,1,n) {
cin >> forest[i][j];
if (forest[i][j] == 'M') x1 = i, y1 = j;
if (forest[i][j] == 'D') x2 = i, y2 = j;
}
FOR(i,1,n) FOR(j,1,n) {
ong[i][j] = INF;
vis[i][j] = false;
}
queue<pair<int,int>> s;
FOR(i,1,n) FOR(j,1,n)
if (forest[i][j] == 'H') {
ong[i][j] = 0;
vis[i][j] = true;
s.push({i,j});
}
while (!s.empty()) {
auto up = s.front(); s.pop();
int x = up.first, y = up.second;
FOR(d,0,3) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 1 || ny < 1 || nx > n || ny > n) continue;
if (vis[nx][ny]) continue;
if (forest[nx][ny] == 'T' || forest[nx][ny] == 'D') continue;
ong[nx][ny] = ong[x][y] + 1;
vis[nx][ny] = true;
s.push({nx, ny});
}
}
int low = 0, high = 2027, ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) ans = mid, low = mid + 1;
else high = mid - 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}