浙江大学数据结构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 <cmath>
#include <cstdlib>
#include <iostream>
#define MAXSIZE 100
#define r 7.5

typedef 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 < graph->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 < Graph->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) <= D) return true;
	else if (abs(-50 - V.y) <= D) return true;
	else if (abs(50 - V.x) <= D) return true;
	else if (abs(50 - V.y) <= D) return true;
	else return false;
}



LGraph buildGraph(int N)
{	
	/* 创建图并初始化顶点 */
	LGraph Graph = creatGraph(N);
	vertex V, W;
	/* 建立边 */
	//遍历所有边，在遍历过程中，检查是否有能够建立连接的边
	for (int i = 0; i < Graph->Nv; i++)
	{	
		V = Graph->G[i]._POS;
		for (int j = 0; j < Graph->Nv; j++)
		{	
			W = Graph->G[j]._POS;

			if (i == j) continue;
			else if (i == 0 && j != 0)
			{
				//鳄鱼所在的顶点W到中心岛中心的距离 - 中心岛半径r <= james跳跃距离，则建立边
				double d = sqrt(pow(V.x - W.x, 2) + pow(V.y - W.y, 2)) - r;
				if (d <= D)
				{
					ptrToENode newEdge = (ptrToENode)malloc(sizeof(ENode));
					newEdge->V1 = V;
					newEdge->V2 = W;
					insertEdge(Graph, newEdge);
				}
			}
			else if (j == 0 && i != 0)
			{
				//鳄鱼所在的顶点W到中心岛中心的距离 - 中心岛半径r <= james跳跃距离，则建立边
				double d = sqrt(pow(V.x - W.x, 2) + pow(V.y - W.y, 2)) - r;
				if (d <= D)
				{
					ptrToENode newEdge = (ptrToENode)malloc(sizeof(ENode));
					newEdge->V1 = V;
					newEdge->V2 = W;
					insertEdge(Graph, newEdge);
				}
			}
			else
			{
				//两点的距离小于james跳跃距离，则建立边
				double d = sqrt(pow(V.x - W.x, 2) + pow(V.y - W.y, 2));
				if (d <= D)
				{
					ptrToENode newEdge = (ptrToENode)malloc(sizeof(ENode));
					newEdge->V1 = V;
					newEdge->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 << "Yes";
	else
		std::cout << "No";
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

心路历程

不看教程做题效率好低啊~~~~~~
一天做了一道，又是被自己菜哭的一天