QQ登录

只需一步,快速开始

登录 | 立即注册 | 找回密码

主题

帖子

荣誉

VIP至尊会员

Rank: 15Rank: 15Rank: 15

积分
97
查看: 214|回复: 1

图的问题(拯救007),求解错在哪里?

[复制链接]
最佳答案
5 
累计签到:43 天
连续签到:23 天
程序员的救赎 发表于 2018-6-3 16:55:43 2141 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目如下:

7-1 拯救007(100 分)
在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去!(据说当年替身演员被最后一条鳄鱼咬住了脚,幸好穿的是特别加厚的靴子才逃过一劫。)
设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,你需要告诉他是否有可能逃出生天。
输入格式:

首先第一行给出两个正整数:鳄鱼数量 N(≤100)和007一次能跳跃的最大距离 D。随后 N 行,每行给出一条鳄鱼的 (x,y) 坐标。注意:不会有两条鳄鱼待在同一个点上。
输出格式:

如果007有可能逃脱,就在一行中输出"Yes",否则输出"No"。
输入样例 1:

14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
输出样例 1:

Yes
输入样例 2:

4 13
-12 12
12 12
-12 -12
12 -12
输出样例 2:

No


代码如下:


  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;

  4. const int MAX_NUM = 100;    // 最大鳄鱼数量
  5. typedef float Elemtype;

  6. typedef struct ArcNode
  7. {   //  邻接表的边结点
  8.         int adjvex;             // 边结点编号
  9.         struct ArcNode *nextarc;
  10. }ArcNode;

  11. typedef struct VNode
  12. {   //  邻接表的表头数组
  13.         int data;               //  鳄鱼的编号,方便遍历
  14.         Elemtype x;             //  鳄鱼坐标
  15.         Elemtype y;             //  
  16.         ArcNode *firstarc;
  17. } VNode, AdjList[MAX_NUM];

  18. typedef struct
  19. {  // 图
  20.         AdjList vertices;
  21.         int vexnum;
  22. }ALGraph;

  23. bool Judge_Arc(ALGraph G, int i, int j, int dis);
  24. void Create_Arc(ALGraph &G, int i, int j);
  25. void CreatUDG(ALGraph &G, int &D, bool visited[]);
  26. bool Judge_upto_bank(ALGraph G, int v, int D);
  27. void DFS(ALGraph G, int v, int D, int &flag, bool visited[]);
  28. bool Judge_Ver(ALGraph G, int i, int D, bool visited[]);
  29. void Judge_Live_or_Die(ALGraph G, int D, int flag, bool visited[]);

  30. int main()
  31. {
  32.         ALGraph G;
  33.         int D, flag = 0;            // D为最大跳跃距离, flag标记007是否能逃出来,默认为0(不能)
  34.         bool visited[MAX_NUM];      // 标记结点是否被访问过
  35.         CreatUDG(G, D, visited);             // 构造一个图
  36.         Judge_Live_or_Die(G, D, flag, visited);    // 判断007的命运
  37. //        system("pause");
  38. }



  39. bool Judge_Arc(ALGraph G, int i, int j, int dis)
  40. { //  两条鳄鱼构成一条边的条件为鳄鱼之间的距离不大于007的最大跳跃距离
  41.         if (
  42.                 (
  43.                      (G.vertices[i].x - G.vertices[j].x)
  44.                         *(G.vertices[i].x - G.vertices[j].x)
  45.                   +
  46.                          (G.vertices[i].y - G.vertices[j].y)
  47.                         *(G.vertices[i].y - G.vertices[j].y)
  48.                 )
  49.                          <= dis * dis
  50.           )
  51.         {
  52.                 return true;
  53.         }
  54.         else
  55.         {
  56.                 return false;
  57.         }
  58. }

  59. void Create_Arc(ALGraph &G, int i, int j)
  60. {  // 头插法增加邻接表的结点
  61.         ArcNode *p1, *p2;
  62.         p1 = new ArcNode;
  63.         p2 = new ArcNode;

  64.         p1->adjvex = j;
  65.         p1->nextarc = G.vertices[i].firstarc;
  66.         G.vertices[i].firstarc = p1;           
  67.         p2->adjvex = i;                      // 对称性
  68.         p2->nextarc = G.vertices[j].firstarc;
  69.         G.vertices[j].firstarc = p2;
  70. }

  71. void CreatUDG(ALGraph &G, int &D, bool visited[])
  72. {
  73.         int i, k = 0;

  74.         // 点的赋值
  75.         cin >> G.vexnum >> D;
  76.         for (i = 0; i < G.vexnum; ++i)
  77.         {
  78.                  G.vertices[i].data = i;  
  79.                  visited[i] = false;             // 给各个点(鳄鱼)编号,方便遍历
  80.                  G.vertices[i].firstarc = NULL;         // 头插法,尾指针必须赋值为空
  81.         }
  82.         for (i = 0; i < G.vexnum; ++i)
  83.         {
  84.                 cin >> G.vertices[i].x >> G.vertices[i].y;
  85.         }

  86.         // 边的确立
  87.         for (i = 0; i < G.vexnum; ++i)
  88.         {
  89.                 for (int j = 0; j < G.vexnum; ++j)
  90.                 {
  91.                         if (i == j)
  92.                                 continue;
  93.                         else if (Judge_Arc(G, i, j, D))
  94.                         {
  95. //                                cout << G.vertices[i].x << G.vertices[i].y << "第" << ++k << "条边。" << endl;
  96.                                 Create_Arc(G, i, j);
  97.                         }         
  98.                 }
  99.         }
  100. }

  101. bool Judge_upto_bank(ALGraph G, int v, int D)
  102. {   // x, y有一个的绝对值加D的和小于50即可跳上岸
  103.         if ((fabs(G.vertices[v].x) + D) >= 50 || fabs((G.vertices[v].y + D)) >= 50)
  104.         {
  105.                 return true;
  106.         }
  107.         else
  108.         {
  109.                 return false;
  110.         }
  111. }

  112. void DFS(ALGraph G, int v, int D, int &flag, bool visited[])
  113. {
  114.         if (Judge_upto_bank(G, v, D))
  115.         { // 判断是否能从当前结点跳上岸
  116.                 flag = 1;
  117.                 return;
  118.         }
  119.         visited[v] = true;

  120.         ArcNode *p = G.vertices[v].firstarc;
  121.         //for (int w = G.vertices[v].firstarc->adjvex; (w >= 0) && (w < G.vexnum); w = p->adjvex)
  122.         while( p!= NULL )
  123.         {
  124.                 int w = p->adjvex;
  125.                 if (!visited[w])
  126.                 {
  127.                         DFS(G, w, D, flag, visited);
  128.                 }
  129.                 p = p->nextarc;
  130.         }
  131. }

  132. bool Judge_Ver(ALGraph G, int i, int D, bool visited[])
  133. {   // 判断需要遍历的点(007第一步能跳上的点)
  134.         if (!visited[i] && sqrt((G.vertices[i].x * G.vertices[i].x) + (G.vertices[i].y * G.vertices[i].y)) <= (D + 7.5))
  135.         {
  136.                 return true;
  137.         }
  138.         else
  139.         {
  140.                 return false;
  141.         }
  142. }
  143. void Judge_Live_or_Die(ALGraph G, int D, int flag, bool visited[])
  144. {
  145.         for (int i = 0; i < G.vexnum; i++)
  146.         {
  147.                 if (Judge_Ver(G, i, D, visited))
  148.                 {
  149.                         DFS(G, i, D, flag, visited);
  150.                         if (flag == 1)
  151.                 {
  152.                             cout << "Yes";
  153.                             return;
  154.                         }
  155.                 }
  156.         }
  157.         cout << "NO";
  158. }


复制代码



疑点如下:
      我的解法是不是有问题??为什么有一些用例不能通过呢。
      

这是测试结果。。。。

这是测试结果。。。。
楼层
跳转到指定楼层
最佳答案
5 
累计签到:43 天
连续签到:23 天
程序员的救赎  楼主| 发表于 2018-6-3 17:00:01 | 显示全部楼层
补充说明一下要点:
1.两条鳄鱼的距离不大于007的最大跳跃距离则确立一条边
2.按深度优先遍历时,是否遍历的条件是鳄鱼离中心点的距离减去小岛的半径后小于007的最大跳跃距离
3.判断能否跳上岸的条件是当前结点的坐标绝对值至少有一个加上007的最大跳跃距离后大于50

发表回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐 上一条 /1 下一条

    移动客户端下载(未启用)
    微信公众号

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备11014136号

Copyright 2018 鱼C论坛 版权所有 All Rights Reserved.

Powered by Discuz! X3.3 Copyright
© 2001-2018 Comsenz Inc.    All Rights Reserved.

小黑屋|手机版|Archiver|鱼C工作室 ( 粤公网安备 44051102000370号 | 粤ICP备11014136号

GMT+8, 2018-6-25 11:52

快速回复 返回顶部 返回列表