07-图5 Saving James Bond - Hard Version(C++详解)

目录

题干

思路

分步解析

1.图和变量的定义

2.判断函数

3.主函数

4.图的初始化

5.核心算法(Dijkstra)

6.路径的回溯算法

7.寻找符合要求的最短路径

完整代码

题干

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him a shortest path to reach one of the banks. The length of a path is the number of jumps that James has to make.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output Specification:

For each test case, if James can escape, output in one line the minimum number of jumps he must make. Then starting from the next line, output the position (x,y) of each crocodile on the path, each pair in one line, from the island to the bank. If it is impossible for James to escape that way, simply give him 0 as the number of jumps. If there are many shortest paths, just output the one with the minimum first jump, which is guaranteed to be unique.

思路

卡了一个星期，好不容易有点思路，又被测试点四卡死了，现在终于做出来了

题目要求不仅要计算James Bond要跳多少步才能得救，还要打印路径 ，同时最短路径长度还存在相等的情况，相等时要求输出起点离岛最近的那条路径。如此复杂的处理要求我们一定要充分理解最短路径的算法，这里推荐一下《算法笔记》，其中对各种算法的讲解很通俗易懂，姥姥在课程中提到了记录路径的方法却没讲具体的实现，这本书写得很详细。

我采用的核心算法是Dijkstra，用和easy version一样的方法求出最短路径，同时用一个pre数组记录每个节点的前驱，方便打印路径。每次遍历完一个起点之后，进行检查，如果当前上岸的最短路径长度小于之前记录的最短路径长度，那么就更新距离和路径，如果当前上岸的最短路径长度等于之前记录的最短路径长度，那么同样要进行更新。

整个程序还有很多要注意的细微点，下面会进行解析。

分步解析

1.图和变量的定义

•  节点的定义包括四个数据——X,Y轴坐标以及是否能从岛上直接跳到（jump）和是否能上岸(safe)
• Num存储鳄鱼（节点）数量，Step存储跳跃距离
• 数组N用于存储每个节点的信息
• 二维数组G作为图存储每只鳄鱼之间的连通关系
• dist存储从源节点到每个节点的距离
• pre存储从源节点到每个节点要经过的前驱节点
• vis记录当前节点是否被访问过
• diameter为直径，要记录半径的话可以直接记为7，因为浮点数处理起来较为麻烦而且存在精度误差（所有数据的处理都用整型会更加方便）

#include <iostream>
#include <cmath>
#define MAXN 101
#define INF 0xffffff
typedef struct GraphNode
{
int x, y;
bool jump, safe;
}Node;
Node N[MAXN];
int Num, Step, G[MAXN][MAXN], dist[MAXN], pre[MAXN];
bool vis[MAXN] = { false };
const int diameter = 15;

2.判断函数

• 判断由该节点是否可以跳上岸
• 注意这里x和y一定要取绝对值，卡在测试点4就是因为这里错了（无语）

bool isSafe(int x, int y)
{
return abs(x) + Step >= 50 || abs(y) + Step >= 50;
//判断是否可以上岸
}

•  判断该节点能否从岛上直接跳到

bool firstJump(int x, int y)
{
return x * x + y * y <= (Step + diameter / 2) * (Step + diameter / 2);
//判断鳄鱼是否可以作为起点
}

• 判断两个节点之间是否连通

bool canJump(int x1, int y1, int x2, int y2)
{
return abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2) <= Step * Step;	//判断鳄鱼之间是否可以跳跃
}

• 判断哪条鳄鱼离岛更近

bool cmp(int n1, int n2)
{
return N[n1].x * N[n1].x + N[n1].y * N[n1].y > N[n2].x * N[n2].x + N[n2].y * N[n2].y;	//判断哪条鳄鱼离岛更近
}

 3.主函数

• 输入节点坐标，同时通过上述函数来判断该鳄鱼是否可以作为起点和终点

int main()
{
std::cin >> Num >> Step;
for (int i = 0; i < Num; i++) {
std::cin >> N[i].x >> N[i].y;
N[i].safe = isSafe(N[i].x, N[i].y);
N[i].jump = firstJump(N[i].x, N[i].y);
}
initGraph();
saving007();
return 0;
}

4.图的初始化

• 图存储的是节点之间是否存在连通关系，连通则为1，无则为0，上一步已经写好了判断函数，这一步就很简单了

void initGraph()
{
for (int i = 0; i < Num; i++)
for (int j = 0; j < Num; j++)
G[i][j] = G[j][i] = canJump(N[i].x, N[i].y, N[j].x, N[j].y);
}

5.核心算法(Dijkstra)

• 这里我们一定要充分理解Dijkstra算法，此题中我们只需要加一个pre数组存储经过某个节点的前驱节点就行了，所以只需在最后循环中加一步，如果已经熟练掌握该算法了，那么这一步其实是很简单的
• 关于这一算法在上面推荐的那本书中写得很详细，其思路是，一开始将原点到原点的距离设置为0（这是当然的），然后进入循环，循环体中的第一个循环寻找当前距离原点最近的点（dist数组全部初始化为INF——一个极大的数），由于第一轮循环中只有原点的距离为0，且原点未被访问过，所以就从原点开始访问，循环体中的第二个循环则是更新原点到每个节点的距离，如果图G中记录两节点之间连通，则比较是否原点到当前节点的距离是否比原距离短，如果是就更新距离，第二轮循环的时候，由于原点已经被访问过，那么就从未被访问过的且距离原点最近（贪心思想）的节点开始，再来一次，更新距离，如此往复，就能得到从原点到所有节点的最短距离（dist），同时每次都要记录到当前节点所要经过的前驱节点（pre），随后用对pre使用dfs回溯就能得到完整路径。

void Dijkstra(int S)
{
dist[S] = 0;
while (true) {
int u = -1, min = INF;
for (int i = 0; i < Num; i++) {
if (!vis[i] && dist[i] < min) {
u = i;
min = dist[i];
}
}
if (u == -1)return;
vis[u] = true;
for (int j = 0; j < Num; j++) {
if (!vis[j] && G[u][j] && dist[u] + 1 < dist[j]) {
//!vis[j]防止往回走,G[u][i]检查u和i之间是否有路径,对此题来讲路径权值都为1,所以直接+1即可，也可以写成+G[u][i]
dist[j] = dist[u] + 1;
pre[j] = u;
//记录前驱节点
}
}
}
}

6.路径的回溯算法

• 传入的参数为起点、终点和最终路径，递归寻找路径，如果起点和终点没有相遇，就使用path[D]去找终点的前驱节点，直到起点与终点相同，就开始回退，逆序打印所有前驱节点就能得到整条路径

void printPath(int S, int D, int* path)
//DFS打印路径,从终点开始回溯
{
if (S == D) {
//如果回到起点
std::cout << N[S].x << ' ' << N[S].y << std::endl;
//先打印起点
return;
}
printPath(S, path[D], path);
//开始回溯
std::cout << N[D].x << ' ' << N[D].y << std::endl;;
//逆序打印前驱节点
}

7.寻找符合要求的最短路径

• 首先我们要处理一下一跳上岸的特殊情况（你是正常人吗） 
• 然后用min来记录到目前为止找到的路径中最短路径的长度，如果min与当前路径长度相同，我们再来通过我们之前写的cmp函数来比较那个起点离岛更近，然后更新min，并且每次更新min时，我们用path数组来拷贝当前的pre，更新路径，同时不要忘记记录当前路径的起点S和终点D
• 最后注意，我们得到的min是不包括起跳和上岸的最后一跳的，所以最后应该+2

void saving007()
{
if (42 <= Step) {
//处理一跳上岸的特殊情况
std::cout << 1;
return;
}
int min = INF, S, D, path[MAXN];
//记录最短路径长度
for (int i = 0; i < Num; i++) {
if (N[i].jump) {
//找起点(可以跳上的第一只鳄鱼)
for (int j = 0; j < Num; j++) {
//初始化vis,dist,pre
vis[j] = false;
dist[j] = INF;
pre[j] = j;
}
Dijkstra(i);
for (int j = 0; j < Num; j++) {
//找终点(safe==1的鳄鱼)
if (N[j].safe && min > dist[j]) {
//如果到这条鳄鱼的路径比上一次记录的最短路径短
min = dist[j];
//更新最短路径长度
S = i;
//记录新起点
D = j;
//记录新终点
for (int k = 0; k < Num; k++)
//copy最短路径
path[k] = pre[k];
}
else if (N[j].safe && dist[j] != INF && min == dist[j] && cmp(S, i)) {	//如果当前路径长度与上一个最短路径长度相同,检查是否离岛更近
S = i;
//如果离岛更近，更新起点
D = j;
//更新终点
for (int k = 0; k < Num; k++)
//copy最短路径
path[k] = pre[k];
}
}
}
}
if (min == INF)
std::cout << 0;
else {
std::cout << min + 2 << std::endl;	//题目要求输出的是007跳的次数,min记录的是从第一条鳄鱼到最后一条鳄鱼之间的跳跃次数而不包括跳到第一条鳄鱼及跳上岸,所以这里应该+2
printPath(S, D, path);
//打印最短路径,S起点,D终点
}
}

完整代码

#include <iostream>
#include <cmath>
#define MAXN 101
#define INF 0xffffff
typedef struct GraphNode
{
int x, y;
bool jump, safe;
}Node;
Node N[MAXN];
int Num, Step, G[MAXN][MAXN], dist[MAXN], pre[MAXN];
bool vis[MAXN] = { false };
const int diameter = 15;
bool isSafe(int x, int y)
{
return abs(x) + Step >= 50 || abs(y) + Step >= 50;
//判断是否可以上岸
}
bool firstJump(int x, int y)
{
return x * x + y * y <= (Step + diameter / 2) * (Step + diameter / 2);
//判断鳄鱼是否可以作为起点
}
bool canJump(int x1, int y1, int x2, int y2)
{
return abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2) <= Step * Step;	//判断鳄鱼之间是否可以跳跃
}
bool cmp(int n1, int n2)
{
return N[n1].x * N[n1].x + N[n1].y * N[n1].y > N[n2].x * N[n2].x + N[n2].y * N[n2].y;	//判断哪条鳄鱼离岛更近
}
void initGraph()
{
for (int i = 0; i < Num; i++)
for (int j = 0; j < Num; j++)
G[i][j] = G[j][i] = canJump(N[i].x, N[i].y, N[j].x, N[j].y);
}
void Dijkstra(int S)
{
dist[S] = 0;
while (true) {
int u = -1, min = INF;
for (int i = 0; i < Num; i++) {
if (!vis[i] && dist[i] < min) {
u = i;
min = dist[i];
}
}
if (u == -1)return;
vis[u] = true;
for (int j = 0; j < Num; j++) {
if (!vis[j] && G[u][j] && dist[u] + 1 < dist[j]) {
//!vis[j]防止往回走,G[u][i]检查u和i之间是否有路径,对此题来讲路径权值都为1,所以直接+1即可，也可以写成+G[u][i]
dist[j] = dist[u] + 1;
pre[j] = u;
//记录前驱节点
}
}
}
}
void printPath(int S, int D, int* path)
//DFS打印路径,从终点开始回溯
{
if (S == D) {
//如果回到起点
std::cout << N[S].x << ' ' << N[S].y << std::endl;
//先打印起点
return;
}
printPath(S, path[D], path);
//开始回溯
std::cout << N[D].x << ' ' << N[D].y << std::endl;;
//逆序打印前驱节点
}
void saving007()
{
if (42 <= Step) {
//处理一跳上岸的特殊情况
std::cout << 1;
return;
}
int min = INF, S, D, path[MAXN];
//记录最短路径长度
for (int i = 0; i < Num; i++) {
if (N[i].jump) {
//找起点(可以跳上的第一只鳄鱼)
for (int j = 0; j < Num; j++) {
//初始化vis,dist,pre
vis[j] = false;
dist[j] = INF;
pre[j] = j;
}
Dijkstra(i);
for (int j = 0; j < Num; j++) {
//找终点(safe==1的鳄鱼)
if (N[j].safe && min > dist[j]) {
//如果到这条鳄鱼的路径比上一次记录的最短路径短
min = dist[j];
//更新最短路径长度
S = i;
//记录新起点
D = j;
//记录新终点
for (int k = 0; k < Num; k++)
//copy最短路径
path[k] = pre[k];
}
else if (N[j].safe && dist[j] != INF && min == dist[j] && cmp(S, i)) {	//如果当前路径长度与上一个最短路径长度相同,检查是否离岛更近
S = i;
//如果离岛更近，更新起点
D = j;
//更新终点
for (int k = 0; k < Num; k++)
//copy最短路径
path[k] = pre[k];
}
}
}
}
if (min == INF)
std::cout << 0;
else {
std::cout << min + 2 << std::endl;	//题目要求输出的是007跳的次数,min记录的是从第一条鳄鱼到最后一条鳄鱼之间的跳跃次数而不包括跳到第一条鳄鱼及跳上岸,所以这里应该+2
printPath(S, D, path);
//打印最短路径,S起点,D终点
}
}
int main()
{
std::cin >> Num >> Step;
for (int i = 0; i < Num; i++) {
std::cin >> N[i].x >> N[i].y;
N[i].safe = isSafe(N[i].x, N[i].y);
N[i].jump = firstJump(N[i].x, N[i].y);
}
initGraph();
saving007();
return 0;
}

总算写出来了，太不容易了（歇菜）

最后

以上就是天真往事为你收集整理的07-图5 Saving James Bond - Hard Version(C++详解)的全部内容，希望文章能够帮你解决07-图5 Saving James Bond - Hard Version(C++详解)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。