Problem B
Gopher and Hawks
Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

A gopher sits in a hole located at (xs, ys) and wants to get to a hole located at (xt, yt). The gopher can run at a constant speed of v m/sec. However, if the gopher is outside of a hole for more than a m minutes he will become a supper to hawks flying over the holes. Can the gopher make it?

Input 

The input file contains several sets of input. The description of each set is given below:

The first line of each set contains two positive integer numbers: v -- gopher's speed in meters per second and m -- the time after which the gopher becomes prey to hawks if he stays outside a hole. The second line of input contains two floating-point numbers: the (xs, ys) coordinates of the gopher’s starting hole. The third line contains the (xt, yt) coordinates of the target hole. Each Subsequent line of input contains two floating point numbers: the (x,y) coordinates of a gopher hole. All distances are in meters, to the nearest mm. A blank line terminates the input for each set.

The last input set starts with a line containing two zeroes. This set should not be processed.

Output 

For each set of input produce one line of output. The description of this line is given below:

If the gopher can make it to the target hole, the output line should read "Yes, visiting n other holes.", where n is the minimal number of intermediate holes the gopher has to visit. If the gopher cannot make it the output line should read "No." There are not more than 1000 gopher holes and all coordinates are between -10000 and +10000. See the sample input and output for details.

Sample Input                             Output for Sample Input

3 1

0.000 0.000

500.000 0.000

179.000 0.000

358.000 0.000

5 1

0.000 0.000

0.000 550.000

179.000 0.000

0.000 301.000 

0 0

Yes, visiting 2 other holes.

No.

Problemsetter: Piotr Rudnicki, CS Department, University of Alberta


題目描述：

老鼠不可以超過洞外 m 秒，否則會被老鷹抓走，因此他必須先經過幾個洞，之後再次出發。
求最少經過的洞之後抵達目地的。

題目解法：

先將圖建出來，然後跑一次 BFS。


#include <stdio.h>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
double px[1005], py[1005];
int main() {
    int v, m, i, j, k;
    char s[105];
    while(scanf("%d %d", &v, &m) == 2) {
        if(v == 0 && m == 0)    break;
        int len = v*m*60, n = 2;
        scanf("%lf %lf", &px[0], &py[0]);
        scanf("%lf %lf", &px[1], &py[1]);
        while(getchar() != '\n');
        while(gets(s) && s[0] != '\0') {
            sscanf(s, "%lf %lf", &px[n], &py[n]);
            n++;
        }
        queue<int> Q;
        int dist[1005] = {}, x;
        dist[0] = 1;
        Q.push(0);
        while(!Q.empty()) {
            x = Q.front(), Q.pop();
            for(i = 0; i < n; i++) {
                if(hypot(px[i]-px[x], py[i]-py[x]) < len) {
                    if(dist[i] == 0) {
                        dist[i] = dist[x]+1;
                        Q.push(i);
                    }
                }
            }
            if(dist[1]) break;
        }
        if(dist[1])
            printf("Yes, visiting %d other holes.\n", dist[1]-2);
        else
            puts("No.");

    }
    return 0;
}