题目链接：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 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           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
         
           vec; 28 vector
          
            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
           
            = 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
            
             > 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 else127 cout << "No" << endl;128 129 return 0;130 }
            
           
          
         
        
       
      
     

AC成果：