中国大学MOOC数据结构基础习题集、052、Saving James Bond Easy Version

题目链接：http://www.patest.cn/contests/mooc-ds/05-2

题目分析：这是一道考察图的深度优先遍历的一道题，题目的背景是007。相信听过陈老师的课，都对这道题的背景有所了解。如果没有认真听或者忘记的话，我再重复一次好了。

　　007处在孤岛上，孤岛的半径为15米，孤岛的范围就是[±15, ±15]。池塘的范围是[±50, ±50]，池塘中有若干条鳄鱼，他的数量以及坐标都通过输入给了出来。007的跳跃距离也通过输入给了出来。要求的计算出是007能否通过不断“踩鳄鱼”来逃出生天呢？

　　输入：鳄鱼的数量+007的跳跃半径+鳄鱼的坐标。

　　输出：Yes能逃出，No不能逃出。

特别说明：

　　1. 不需要建立图这种数据结构，只需要用数组把坐标信息存起来就可以了。

　　2. 需要有一个额外的visited数组，来存储结点是否被访问过。

　　3. 孤岛也是一个结点，它的坐标是(0,0)。在孤岛上是“第一跳”，因为007可以在岛的任一地方起跳，所以要特殊考虑。

　　4. 做深度优先遍历时，不需要像以前一样用for循环对图中的每一个结点进行遍历，只需要从孤岛这一个结点开始遍历就可以了。

　　5. 另外，为了避免程序中出现“魔数”，最好把15,50这样的数在最开始用宏定义，程序的可读性和可移植性就变的更好了！

建议测试如下数据：

　　5 13 -12 12 12 12 -12 -12 12 -12 50 50　　

代码分析：

　　头文件声明：1-7

　　定义所用数据结构的名字及解释：8-14（注释中），24-28（全局变量的定义）

　　定义“坐标”结构体：17-22（这里用double是方便计算距离，计算两点之间的距离时，要用sqrt开平方，计算结果是浮点数）

　　计算“距离”的函数：30-44（第一跳要特殊计算）

　　判断是否安全的函数：46-66（第一跳要特殊计算）

　　深度优先遍历：66-95（具体已经写到程序的注释中）

　　主函数，处理输入以及输出：97-130　　

  1 #include <iostream>
  2 #include <vector>
  3 #include <cmath>
  4 #include <cstdlib>
  5 
  6 #define FIRSTSTEP 15
  7 #define BORDER 50
  8 /*
  9  * FIRSTSTEP 孤岛的半径，第一步能迈出多少米
 10  * BORDER 边界范围[±BORDER/2, ±BORDER/2]
 11  * vec 存储坐标信息 nNum 鳄鱼的数量 dis 007的跳跃距离
 12  * visited 存储是否访问过信息
 13  * firstStep/firstJudge 标记是否为第一次
 14  */
 15 using namespace std;
 16 
 17 struct pos
 18 {
 19     double x;
 20     double y;
 21     pos(double a, double b):x(a),y(b) {}
 22 };
 23 
 24 bool firstStep = true;
 25 bool firstJudge = true;
 26 int nNum, dis;
 27 vector<pos> vec;
 28 vector<bool> visited;
 29 
 30 double Distance(pos p1, pos p2)
 31 {
 32     double xx = (p1.x - p2.x) * (p1.x - p2.x);
 33     double yy = (p1.y - p2.y) * (p1.y - p2.y);
 34     // 第一次是在中心，半径为15的岛上
 35     if(firstStep == true)
 36     {
 37         return dis + FIRSTSTEP - sqrt(xx + yy);
 38         firstStep = false;
 39     }
 40     else
 41     {
 42         return dis - sqrt(xx + yy);
 43     }
 44 }
 45 
 46 bool judge(pos s)
 47 {
 48     if(firstJudge == true)
 49     {
 50         firstJudge = false;
 51         if(fabs(s.x-BORDER)<=dis+FIRSTSTEP
 52                 ||fabs(s.x+BORDER)<=dis+FIRSTSTEP
 53                 ||fabs(s.y-BORDER)<=dis+FIRSTSTEP
 54                 ||(s.y+BORDER)<=dis+FIRSTSTEP)
 55             return true;
 56     }
 57     else
 58     {
 59         if(fabs(s.x-BORDER)<=dis
 60                 ||fabs(s.x+BORDER)<=dis
 61                 ||fabs(s.y-BORDER)<=dis
 62                 ||(s.y+BORDER)<=dis)
 63             return true;
 64     }
 65     return false;
 66 }
 67 
 68 
 69 bool DFS(int i)
 70 {
 71     // 标记当前结点已经被访问过了
 72     visited[i] = true;
 73     // 是否安全逃出
 74     bool answer = false;
 75     // 如果距离足够逃离，则逃离
 76     if(judge(vec[i]) == true)
 77     {
 78         answer = true;
 79     }
 80     else
 81     {
 82         for(int j=0; j<vec.size(); j++)
 83         {
 84             // 如果没有被访问过，距离也够，那就继续做深度优先遍历
 85             if(visited[j] == false && Distance(vec[i], vec[j]) >= 0)
 86             {
 87                 firstStep = false;
 88                 answer = DFS(j);
 89                 if (answer == true)
 90                     break;
 91             }
 92         }
 93     }
 94     return answer;
 95 }
 96 
 97 int main()
 98 {
 99     cin >> nNum >> dis;
100     if(dis + FIRSTSTEP >= BORDER)
101     {
102         cout << "Yes" << endl;
103         return 0;
104     }
105     // 先把孤岛这个结点放进去
106     vec.push_back(pos(0, 0));
107     visited.push_back(false);
108     // 用邻接矩阵存储图
109     for(int i=0; i<nNum; i++)
110     {
111         double a, b;
112         cin >> a >> b;
113         vec.push_back(pos(a,b));
114         visited.push_back(false);
115     }
116     bool answer = false;
117     // 深度优先遍历，从数字最小的结点开始遍历
118     int i = 0;
119     if(!visited[i])
120     {
121         answer = DFS(i);
122     }
123     
124     if (answer == true)
125         cout << "Yes" << endl;
126     else
127         cout << "No" << endl;
128 
129     return 0;
130 }

AC成果：