题解：P9116 [IOI 2009] Mecho

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 805;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int n, s, sx, sy;
int dis[N][N];

bool vis[N][N];

char c[N][N];

struct node {
	int x, y, cnt;
};

void bfs() {
	memset(dis, 0x3f3f3f3f, sizeof dis);
	queue<node> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (c[i][j] == 'H') {
				q.push({i, j, 0});
			}
		}
	}
	while (!q.empty()) {
		int nx = q.front().x, ny = q.front().y, nc = q.front().cnt;
		q.pop();
		if (vis[nx][ny] == 1) {
			dis[nx][ny] = min(nc * s, dis[nx][ny]);
			continue;
		}
		vis[nx][ny] = 1;
		dis[nx][ny] = nc * s;
		for (int i = 0; i < 4; i++) {
			int x = nx + dx[i], y = ny + dy[i];
			if (c[x][y] == 'T' || c[x][y] == 'D' || x < 1 || x > n || y < 1 || y > n) {
				continue;
			}
			q.push({x, y, nc + 1});
		}
	}
}

bool check(int xx) {
	memset(vis, 0, sizeof vis);
	if (xx > dis[sx][sy]) {
		return 0;
	}
	bool bo = 0;
	queue<node> q;
	q.push({sx, sy, xx});
	vis[sx][sy] = 0;
	while (!q.empty()) {
		int nx = q.front().x, ny = q.front().y, nc = q.front().cnt;
		q.pop();
		if (c[nx][ny] == 'D') {
			bo = 1;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int x = nx + dx[i], y = ny + dy[i];
			if (c[x][y] == 'T' || c[x][y] == 'H' || x < 1 || x > n || y < 1 || y > n || vis[x][y] == 1 || nc + 1 > dis[x][y]) {
				continue;
			}
			q.push({x, y, nc + 1});
			vis[x][y] = 1;
		}
	}
	return (bo == 1);
}

signed main() {
	cin >> n >> s;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> c[i][j];
			if (c[i][j] == 'M') {
				sx = i;
				sy = j;
			}
		}
	}
	bfs();
	int l = 1, r = n * n*s, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid) == 1) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	if (ans == -1)
		cout << -1;
	else
		cout << (ans + s - 1) / s - 1;//要向上取整
	return 0;
}