`
从此醉
  • 浏览: 1034465 次
  • 性别: Icon_minigender_1
  • 来自: US
社区版块
存档分类
最新评论

hdu 1245 Saving James Bond

 
阅读更多

点击打开链接hdu 1245


思路:最短路+floyd

分析:
1 题目讲的是有一个湖100x100这个人刚开始在一个直径为15的圆心在原点的园内,然后要通过跳跃的方式问我们他是否能够到达岸边。如果可以求出最短的路径和步数
2 很明确就是最短路问题。但是这个时候问题来了,起点和终点是在哪里,所以我们采用的是将原点作为起点,岸边做为终点。知道了起点和终点,我们就可以求最短路,但是这个时候会碰到另外一个问题,边的长度。对于这个问题,我们是采取的方法是将这些点分成三类。1类:起点 2类:终点 3类:其它点 ,那么我们就可以分别对这三类的点求出它和其它点的距离。

注意事项:
1 输入的数据中,点的范围可能会在园内或在湖外,所以在输入的时候要判断点是否合法。
2 这一题精度要求很严格,一些比较之类的要注意精度问题
3 注意n = 0 的情况,这里如果n = 0,但是d > 42.5 是可以跳出去的。但是只要有乌龟,这个人就必须通过踩在乌龟上面跳出去,所以n = 0是比较特殊的。
4 n不大所以什么方法都可以做
5 求所需几步的时候利用一个setp[][]数组,首先初始户为0然后将可以到达的点标记为1,最后只要在更新dis[][]的时候更新即可。


代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF
#define eps 1e-12

int n;
double d;
double dis[MAXN][MAXN];
int setp[MAXN][MAXN];
struct Point{
   int x;
   int y;
}p[MAXN];

/*初始话边*/
void init(){
   memset(setp , 0 , sizeof(setp));/*初始话为0*/
   /*第三类的点*/
   for(int i = 2 ; i < n ; i++){
      for(int j = 2 ; j < n ; j++){
         double tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x);
         double tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y);
         double tmp = sqrt(tmp_x + tmp_y);
         if(tmp-d <= eps){
            dis[i][j] = tmp;
            setp[i][j] = 1;
         }
         else
            dis[i][j] = INF;
      }
      dis[i][i] = 0;
   }
   /*第一类点*/
   dis[1][1] = 0;
   dis[1][n] = dis[n][1] = INF;
   for(int i = 2 ; i < n ; i++){
      double tmp = sqrt((p[i].x)*(p[i].x)*1.0+(p[i].y)*(p[i].y)*1.0);
      if(tmp-7.5-d <= eps){/*注意要减去7.5*/
        dis[1][i] = dis[i][1] = tmp-7.5;
        setp[1][i] = setp[i][1] = 1;
      }
      else
        dis[1][i] = dis[i][1] = INF;
   }
   /*第二类点*/
   dis[n][n] = 0;
   for(int i = 2 ; i < n ; i++){
      int a = 50-abs(p[i].x);
      int b = 50-abs(p[i].y);
      int min = a < b ? a : b;
      if(min-d <= eps){
        dis[i][n] = dis[n][i] = min;
        setp[i][n] = setp[n][i] = 1;
      }
      else
        dis[i][n] = dis[n][i] = INF;
   }
}

/*floyd算法*/
void floyd(){
   for(int k = 1 ; k <= n ; k++){
      for(int i = 1 ; i <= n ; i++){
         for(int j = 1 ; j <= n ; j++){
            if(dis[i][j]-(dis[i][k]+dis[k][j]) >= eps){
              dis[i][j] = dis[i][k]+dis[k][j];
              setp[i][j] = setp[i][k] + setp[k][j];/*更新数组*/
            }
         }
      }
   }
}

int main(){
   int a , b , j;
   while(scanf("%d %lf" , &n , &d) != EOF){
       j = 2;/*默认1为起点,j从2开始*/
       for(int i = 0 ; i < n ; i++){
          scanf("%d%d" , &a , &b);
          if(abs(a) < 8 && abs(b) < 8 || abs(a) > 50 && abs(b) > 50)/*如果不合法就跳过*/
            continue;
          p[j].x = a;
          p[j++].y = b;
       }
       n = j;
       if(!n){/*判断n是否为0*/
          if(d-42.5 >= eps)
            printf("42.50 1\n");
          else
            printf("can't be saved\n");
          continue;
       }
       init();
       floyd();
       if(dis[1][n] != INF)/*是否可以跳出去*/
         printf("%0.2lf %d\n" , dis[1][n] , setp[1][n]);
       else
         printf("can't be saved\n");
   }
   return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics