利用BFS解决拯救007问题 -- 数据结构

题目：

7-1 拯救007 (30 分)

在老电影“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：

输出样例 1：

Yes

输入样例 2：

输出样例 2：

No

分析：

1. 首先这看上去是一道图的题目，但实际上是不需要将整个图给存储起来也能够完成题目的要求（当然存起来也可以做），

只需要利用好题目所给的坐标就可了！

2. 值得注意的一点是虽然 N（≤100），但如果化为直观图的话，这是一个 101 * 101 的一个矩阵。

3. 拯救007在这里用DFS和BFS都能够解决，这里采用了BFS算法，下面是整道题的思路：

①从池心岛边缘开始，将能够一步到达的坐标（鳄鱼的位置）入队

记作A集合（红点所示）

②A集合中任意选一个点a（队列首元素出队实现）

判断a点能否一步逃离鳄鱼池：

（1）如果可以，输出 Yes 结束程序

（2）如果不可以，从a开始，将能够一步到达的坐标入队，直至A中所有元素遍历完成。

记作B集合（红点所示）

③B集合重复A集合操作。

循环结束条件：（1）找到符合条件的坐标，输出Yes

（2）遍历所有坐标，无符合条件的，输出No

代码：

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 #define max 101

 typedef struct point{

     int x, y;//坐标(x,y)

     double dis;//点point到圆心(0,0)距离

 }point;

 int visit[max] = {};//全局变量visit[]，记录该坐标是否被访问过

 void input(point *p, int n);

 void BFS(point *p, int n, int step);

 int main(){

     int n, step;

     cin>>n>>step;

     point p[max];

     memset(p, , sizeof(p));

     input(p, n);

     //若一步就可以跨出去

     if(step >= -7.5){

         cout<<"Yes";

     }else BFS(p, n, step);//不能一步就跨出去的话 

     return ;

 }

 //输入函数：输入数据

 void input(point *p, int n)

 {

     for(int i=; i<n; i++){

         cin>>p[i].x>>p[i].y;//输入鳄鱼的坐标

         p[i].dis = sqrt(p[i].x*p[i].x + p[i].y*p[i].y) - 7.5;//计算并存储鳄鱼到池心岛的最近距离

     }

 }

 //层次遍历

 void BFS(point *p, int n, int step)

 {

     //先将第一步能够够得着的坐标入队列

     queue<point> qu;

     for(int i=; i<n; i++){

         if(p[i].dis<=step){

             qu.push(p[i]);

             visit[i] = ;

         }

     }

     while(qu.size() != ){

         //判断出队的点A下一步能不能够跨出去

         point mark = qu.front();

         if(mark.x+step >=  || mark.x-step <= - || mark.y+step >= || mark.y-step <=-){

             cout<<"Yes";

             return;

         }

         qu.pop();

         // A点下一步能够够得着的点入队

         for(int i=; i<n; i++){

             if(visit[i] !=  && sqrt((mark.x-p[i].x)*(mark.x-p[i].x) + (mark.y-p[i].y)*(mark.y-p[i].y)) <= step){

                 qu.push(p[i]);

                 //入队标记

                 visit[i] = ;

             }

         }

     }

     cout<<"No";

 }

总结：

拯救007这个题目是一道很好的拓展眼界的题目吧，刚接触这道题的时候会被课本的知识限制住了想象空间，

总觉得做图的题目都要先将图给存储起来，才好做下一步的操作。

还是学的太少，被自己的知识绊住了脚步。

:D 加油！

巴特西