浙江大学数据结构MOOC-课后习题-第六讲-图2 Saving James Bond - Easy Version

题目汇总

浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

测试点

思路分享

①解题思路概览

我的想法是，先建立一个图，然后再利用DFS或者BFS来遍历判断当前顶点能否跳到岸上去

②怎么建图？

• 首先要考虑采用什么数据结构来存储图？

  由于题目中的坐标是存在负数的，所有坐标不好和邻接矩阵数组下标一一对应，因此我选择使用邻接表来存储图

• 接下来要考虑的是，怎么来建立顶点？

  我这里是将所有鳄鱼，以及湖心都作为了节点，因此建立的顶点数要在输入的N的基础上再加1

• 那么怎么建立边呢？

  我们要注意到题目中有一个条件是james的跳跃距离D，只要他目前所处的位置到任意一个顶点的距离小于等于D，那么他就能跳过去，然后就可以建立一条边（后续判断是否上岸也是根据这个D来进行判断）（本考研鼠鼠对上岸这个词有点敏感了hhhh）

  但需要注意一点，由于我把湖心也作为了顶点，所以它和鳄鱼之间也要建立边。它和鳄鱼之间的距离的计算公式中，还要减去中心岛的半径（题目中是7.5）

  ③怎么遍历所有节点呢

  遍历所有节点有两种方式：BFS或者DFS；由于我想到BFS要使用队列，感觉会麻烦一点，所以选择了DFS。

  DFS的代码逻辑就是：

  • 先判断当前节点是否已访问过；（因此要建立一个数组来存储当前顶点是否被访问过）
  • 再访问当前节点（在本题中这一步就是判断是否能够逃脱，具体怎么判断请看后文）
  • 然后遍历访问当前节点的所有邻接点（这一步使用循环+DFS递归）

    ④怎么判断是否能够逃脱上岸呢

    首先我们以湖心为坐标原点，画一个xy坐标系，x的取值范围：[-50,50]，y的取值范围：[-50,50]；

    由此我们可以得到一个边界，我们要是能够从当前顶点跳到边界，那么就代表逃脱成功了，那么怎么计算呢？

    其实就是利用以下几个式子abs(50-x)、abs(50-y)、abs(-50-x)、abs(-50-y)（这就是当前顶点到4条边界的距离）。将这几个值和上文提到的D进行比较，如果值小于等于D，那么就能成功逃脱啦！

    ⑤其他注意事项

    把湖心作为顶点后，记得在创建数组时，数组的大小要在题目的输入N的基础上加1喔

    代码展示

    #include #include #include #define MAXSIZE 100#define r 7.5typedef int pos;int D;int check[MAXSIZE + 1] = { 0 };//检查节点是否被访问过int res = 0;/* 顶点 */struct vertex{pos x, y;};/* 边 */struct ENode{vertex V1, V2;};typedef ENode* ptrToENode;typedef ptrToENode Edge;/* 邻接表的链表节点 */struct AdjNode{vertex AdjV;/* 邻接点位置 */AdjNode* next;};typedef AdjNode* ptrToAdjNode;/* 邻接表的表头数组 */typedef struct VNode{ptrToAdjNode FirstEdge;vertex _POS;}AdjList[MAXSIZE + 1];/* 图的定义 */struct GNode{int Nv;/* 顶点数 */int Ne;/* 边数 */AdjList G;//邻接表};typedef GNode* ptrToGNode;typedef ptrToGNode LGraph;/* 创建并初始化一个图 */LGraph creatGraph(int Nv){vertex V;LGraph graph = (LGraph)malloc(sizeof(GNode));graph->Nv = Nv;graph->Ne = 0;graph->G[0]._POS = { 0 , 0 };graph->G[0].FirstEdge = NULL;for (int i = 1; i Nv; i++){std::cin >> V.x >> V.y;//将鳄鱼位置保存在表头数组中graph->G[i]._POS = V;graph->G[i].FirstEdge = NULL;}return graph;}/* 查找V在表头数组中的下标 */int findIndex(LGraph Graph, vertex V){for (int i = 0; i Nv; i++){if (Graph->G[i]._POS.x == V.x && Graph->G[i]._POS.y == V.y)return i;}}/* 向图中插入一条边 */void insertEdge(LGraph Graph, Edge E){vertex V = E->V1;vertex W = E->V2;int i = findIndex(Graph, V);/* 为W建立新的邻接点空间，并将其插到V的表头 */ptrToAdjNode newNode = (ptrToAdjNode)malloc(sizeof(AdjNode));newNode->AdjV = W;newNode->next = Graph->G[i].FirstEdge;Graph->G[i].FirstEdge = newNode;Graph->Ne++;}/* 检查当前节点能否逃脱 */bool checkOut(vertex V){if (abs(-50 - V.x) /* 创建图并初始化顶点 */LGraph Graph = creatGraph(N);vertex V, W;/* 建立边 *///遍历所有边，在遍历过程中，检查是否有能够建立连接的边for (int i = 0; i V2 = W;insertEdge(Graph, newEdge);}}}}return Graph;}int visit[MAXSIZE + 1] = { 0 };void DFS(LGraph Graph, vertex V){ptrToAdjNode W;/* 检查当前顶点是否被访问过 */int i = findIndex(Graph, V);if (visit[i] != 0) return;visit[i] = 1;/* 检查当前顶点能否使james上岸 */if (checkOut(V)){res = 1;//存储结果的变量1：表示成功逃脱return;}/* 访问V的所有邻接点 */for (W = Graph->G[i].FirstEdge; W != NULL; W = W->next){i = findIndex(Graph, W->AdjV);if (visit[i] != 1)DFS(Graph, W->AdjV);}}int main(){int N;std::cin >> N >> D;LGraph Graph = buildGraph(N + 1);DFS(Graph, Graph->G[0]._POS);if (res)std::cout