题解：P9116 [IOI 2009] Mecho

yzx_yzx · 2025-10-09 11:40:36 · 题解

题目描述：

求小熊在起点的最大等待时间，保证小熊 Mecho 能在不被扎的情况下回到家。

题目分析：

在小熊每分钟走 1 格的情况下：

• 用 BFS 求出蜜蜂到其他点的距离，存在 dis 数组中。
• 二分答案等待最大值，BFS 检查能否到达家里。

对于题目给的小熊一秒能走 s 格。

不难想到把小熊一秒走 s 格转换成蜜蜂 s 秒走一格。

这样最后的答案要除以 s，因为改为蜜蜂 s 秒走一格之后所有步数也都放大了 s 倍（不理解的可以把 dis 数组画出来）。

代码：

#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;
}