题意分析

这个问题本质上是一个图论中的最短路径问题，需要考虑时间限制和最少中间洞数量。我们需要判断地鼠是否能在规定时间内从起点洞到达目标洞，并求出需要经过的最少中间洞数量。

解题思路

为了解决地鼠能否从起点洞安全到达目标洞的问题，我们需要考虑地鼠在洞外移动时的时间限制。地鼠的移动速度是每秒 (v) 米，但每次从一个洞移动到另一个洞的时间不能超过 (a) 分钟（即 (m) 分钟），否则会被老鹰捕食。因此，我们需要检查是否存在一条从起点到目标的路径，其中每一段移动的距离不超过最大允许距离 (D_{\text{max}} = v \times m \times 60) 米。

方法思路

1. 问题建模：将每个地鼠洞视为图中的节点。如果两个洞之间的距离不超过 (D_{\text{max}})，则在它们之间添加一条无向边。
2. 构建邻接表：计算所有洞对之间的距离（使用平方距离比较以避免浮点数精度问题），并根据最大允许距离 (D_{\text{max}}) 构建图的邻接表。
3. BFS搜索最短路径：使用广度优先搜索（BFS）从起点洞开始搜索到目标洞的最短路径（以边数计）。BFS 保证找到的路径具有最少的边数，从而最小化经过的中间洞数量。
4. 输出结果：如果存在路径，计算中间洞的数量（跳数减 1）；否则输出无法到达。

解决代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

int main() {
    int v, m;
    cin >> v >> m;

    double xs, ys, xt, yt;
    cin >> xs >> ys;
    cin >> xt >> yt;

    vector<Point> holes;
    holes.push_back(Point(xs, ys)); // Start hole at index 0
    holes.push_back(Point(xt, yt)); // Target hole at index 1

    double x, y;
    while (cin >> x >> y) {
        holes.push_back(Point(x, y));
    }

    int n_holes = holes.size();

    long long T_max_seconds = static_cast<long long>(v) * m * 60;
    long long D_max_sq = T_max_seconds * T_max_seconds;

    vector<vector<int>> adj(n_holes);
    for (int i = 0; i < n_holes; ++i) {
        for (int j = i + 1; j < n_holes; ++j) {
            double dx = holes[i].x - holes[j].x;
            double dy = holes[i].y - holes[j].y;
            double dist_sq = dx * dx + dy * dy;
            if (dist_sq <= static_cast<double>(D_max_sq)) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    vector<int> dist(n_holes, -1);
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    bool reached_target = false;

    while (!q.empty() && !reached_target) {
        int u = q.front();
        q.pop();
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int neighbor = adj[u][i];
            if (dist[neighbor] == -1) {
                dist[neighbor] = dist[u] + 1;
                q.push(neighbor);
                if (neighbor == 1) {
                    reached_target = true;
                    break;
                }
            }
        }
    }

    if (dist[1] == -1) {
        cout << "No." << endl;
    } else {
        int n_other_holes = dist[1] - 1;
        cout << "Yes, visiting " << n_other_holes << " other holes." << endl;
    }

    return 0;
}

代码解释

1. 输入读取：读取地鼠的速度 (v) 和最大停留时间 (m)（分钟），以及起点洞、目标洞和其他洞的坐标。
2. 距离计算：计算最大允许距离的平方 (D_{\text{max}}^2 = (v \times m \times 60)^2)，避免使用浮点数开方。
3. 邻接表构建：遍历所有洞对，如果平方距离不超过 (D_{\text{max}}^2)，则在邻接表中添加边。
4. BFS搜索：从起点洞（索引 0）开始进行 BFS，记录每个洞的跳数（从起点到该洞的最少边数）。如果搜索到目标洞（索引 1），则标记已到达。
5. 结果输出：如果目标洞未被访问，输出 "No."；否则，计算中间洞的数量（跳数减 1）并输出。

标程

#include<bits/stdc++.h>
using namespace std;
struct Point {
    double x,y;
    Point(double x,double y): x(x), y(y) {}
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int v,m;
    cin >> v >> m;
    double xs,ys,xt,yt;
    cin >> xs >> ys;
    cin >> xt >> yt;
    vector<Point> holes;
    holes.push_back({xs,ys});
    holes.push_back({xt,yt});
    double x,y;
    while(cin >> x >> y){
        holes.push_back({x,y});
    }
    int n_holes = holes.size();
    long long max_second = static_cast<long long>(v) * m * 60;
    long long max_sq = max_second * max_second;
    vector<vector<int>> adj(n_holes);
    for(int i = 0; i < n_holes;i++) {
        for(int j = i + 1; j < n_holes; j++){
            double dx = holes[i].x - holes[j].x;
            double dy = holes[i].y - holes[j].y;
            double dist_sq = dx * dx * dy * dy;
            if(dist_sq <= static_cast<double>(max_sq)){
                adj[i].push_back(i);
                adj[j].push_back(j);
            }
        }
    }
    vector<int> dist(n_holes,-1);
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    bool reach_tag = false;
    while(!q.empty() && !reach_tag){
        int u = q.front();
        q.pop();
        for(int i = 0; i < adj[u].size(); i++){
            int neighbor = adj[u][i];
            if(dist[neighbor] == -1){
                dist[neighbor] = dist[u] + 1;
                q.push(neighbor);
                if(neighbor == 1){
                    reach_tag = true;
                    break;
                }
            }
        }
    }
    if (dist[1] == -1) {
    cout << "No." << endl;
    } else {
    int n_other_holes = dist[1] - 1;
    cout << "Yes, visiting " << n_other_holes << " other holes." << endl;
    }
    return 0;
}

解题思路

这道题目可以抽象为一个图的最短路径问题，目标是找到从起点洞到目标洞的最少中间洞数量，同时满足每次移动的距离不超过地鼠在洞外能存活的最大距离。具体步骤如下：

1. 问题建模：

   • 将每个地鼠洞视为图中的一个节点。
   • 如果两个洞之间的距离不超过 d = v * m * 60（即地鼠在 m 分钟内能跑的最远距离），则在这两个洞之间建立一条无向边（表示地鼠可以双向移动）。
   • 这样，问题转化为在图中从起点洞到目标洞的最短路径问题（最少中间洞数量）。

2. BFS 求最短路径：

   • 使用**广度优先搜索（BFS）**来寻找最短路径，因为 BFS 天然适合求解无权图的最短路径（每次扩展一层，最先到达目标节点的路径一定是最短的）。
   • 初始化 dis[0] = 0（起点洞的编号为 0），其他节点的 dis 设为无穷大。
   • 使用队列进行 BFS，每次从队列取出一个节点，遍历其所有邻接节点，更新它们的距离，并加入队列。

3. 结果输出：

   • 如果目标洞的 dis 仍然是无穷大，说明无法到达，输出 No.。
   • 否则，输出 Yes, visiting n other holes.，其中 n = dis[n] - 1（因为 dis[n] 计算的是总节点数，包括起点和目标，所以中间洞数为 dis[n] - 1）。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define maxn 1111
#define INF 0x3f3f3f3f
struct Edge
{
    int to,next;
}edge[maxn*maxn];
int head[maxn],tot,n=1,vis[maxn],dis[maxn];
struct node
{
    double x,y;
}s,e,p[maxn];
void add(int u,int v)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
double get_dis(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int bfs()
{
    queue<int>que;
    que.push(0);
    dis[0]=0,vis[0]=1;
    for(int i=1;i<=n;i++)
        dis[i]=INF,vis[i]=0;
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=head[u];~i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(!vis[v])
            {
                que.push(v);
                vis[v]=1;
                dis[v]=dis[u]+1;
            }
        }
    }
    return dis[n];
}
int main()
{
    memset(head,-1,sizeof(head));
    tot=0;
    double v,m,d;
    scanf("%lf%lf%lf%lf%lf%lf",&v,&m,&s.x,&s.y,&e.x,&e.y);
    d=v*m*60;
    p[0]=s;
    while(~scanf("%lf%lf",&p[n].x,&p[n].y))n++;
    p[n]=e;
    for(int i=0;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(get_dis(p[i],p[j])<=d)
                add(i,j),add(j,i);
    int ans=bfs();
    if(ans==INF)printf("No.\n");
    else printf("Yes, visiting %d other holes.\n",ans-1);
    return 0;
}