这一个，我认为可以不用DFS, 所以我采用一种建树的方式构造图，整体时间复杂度，较低，但是我也有些问题，随后我用认为，最小N，最小跳，不过是一个鳄鱼罢了，我也实验了，可还是找不到原因。
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 sample 有不成功的分支，连续几次到岸；有可以到岸但跳不过去的，多连通 184 1 答案正确
7 / 7 1 sample 都可以跳到，但不到岸 312 2 答案正确
6 / 6 2 最小N 340 1 答案错误
0 / 3 3 最小跳，人工乱序 368 1 答案错误
0 / 3 4 最大N最小跳，4象限对称，人工乱序 364 2 答案正确
3 / 3 5 都能到岸，但够不着 360 2 答案正确
3 / 3
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 whether or not he can escape.
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, print in a line "Yes" if James can escape, or "No" if not.
Sample Input 1:
14 20 25 -15 -25 28 8 49 29 15 -35 -2 5 28 27 -29 -8 -28 -20 -35 -25 -20 -13 29 -30 15 -35 40 12 12Sample Output 1:
YesSample Input 2:
4 13 -12 12 12 12 -12 -12 12 -12Sample Output 2:
No
我的AC
解题路径：
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>typedef struct Node *List;
struct Node{int data;List Next;
};typedef struct Coordinate *Coordinate;
struct Coordinate{int X;int Y;
};typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{Coordinate Cd;PtrToAdjVNode Brother;PtrToAdjVNode Child;
};typedef struct GNode *LGraph;
struct GNode{bool Up;int N;int D;PtrToAdjVNode Parent;
};bool Build_Graph();
LGraph Init_Graph();
void Insert_VNode(PtrToAdjVNode *Parent, LGraph M, Coordinate *Cd, List Link);
PtrToAdjVNode Add_VNode(Coordinate Cd);
Coordinate* Read_Coordinate(int N);
PtrToAdjVNode Init_AdjVNode(Coordinate Cd);
List Init_Link(int N);
List Creat_Link(int N);
void Delete_Link(List *Node);
bool Dict_E(int D, Coordinate start, Coordinate end);
bool IsSafe(Coordinate Node, int D);int main()
{bool M;M = Build_Graph();if(M){printf("Yes\n");}else{printf("No\n");}return 0;
}LGraph Init_Graph()
{LGraph M;M = (LGraph)malloc(sizeof(struct GNode));M ->Up = false;scanf("%d %d", &(M ->N), &(M ->D));M ->Parent = NULL;return M;
}
bool Build_Graph()
{LGraph M;Coordinate *Cd;List Link;M = Init_Graph();Cd = Read_Coordinate(M ->N);M ->Parent = Init_AdjVNode(Cd[0]);Link = Creat_Link(M ->N);if(IsSafe(Cd[0], (M ->D) + 7.5)) return true;Insert_VNode( &(M ->Parent), M, Cd, Link);return (M ->Up);
}
void Insert_VNode(PtrToAdjVNode *Parent, LGraph M, Coordinate *Cd, List Link)
{PtrToAdjVNode Tag, head, rear;List PtrL;rear = (*Parent);PtrL = Link;while(PtrL ->Next){if(Dict_E((M ->D) + 7.5, Cd[0], Cd[PtrL ->Next ->data])){if(!(rear ->Child)){rear ->Child = Init_AdjVNode(Cd[PtrL ->Next ->data]);if(IsSafe(Cd[PtrL ->Next ->data], M ->D)){M ->Up = true;return ;}rear = rear ->Child;}else{rear ->Brother = Init_AdjVNode(Cd[PtrL ->Next ->data]);if(IsSafe(Cd[PtrL ->Next ->data], M ->D)){M ->Up = true;return ;}rear = rear ->Brother;} Delete_Link(&PtrL);}else{PtrL = PtrL ->Next;}}if(!((*Parent) ->Child)){return ;}Tag = (*Parent) ->Child;head = (*Parent) ->Child;rear = head;while(Link ->Next){PtrL = Link;while(PtrL ->Next){if(Dict_E((M ->D), head ->Cd, Cd[PtrL ->Next ->data])){if(!(rear ->Child)){rear ->Child = Init_AdjVNode(Cd[PtrL ->Next ->data]);if(IsSafe(Cd[PtrL ->Next ->data], M ->D)){M ->Up = true;return ;}rear = rear ->Child;}else{rear ->Brother = Init_AdjVNode(Cd[PtrL ->Next ->data]);if(IsSafe(Cd[PtrL ->Next ->data], M ->D)){M ->Up = true;return ;}rear = rear ->Brother;} Delete_Link(&PtrL);}else{PtrL = PtrL ->Next;}}if(!(head ->Child)){return ;}head = head ->Brother;rear = head;if(!(head)){Tag = Tag ->Child;head = Tag;rear = head;}}return ;
}
bool IsSafe(Coordinate Node, int D)
{return (abs(Node ->X) > 50 - D || abs(Node ->Y) > 50 - D);
}
Coordinate* Read_Coordinate(int N)
{Coordinate *Cd;Cd = (Coordinate*)malloc(sizeof(struct Coordinate) * (N + 1));Cd[0] = (Coordinate)malloc(sizeof(struct Coordinate));Cd[0] ->X = 0;Cd[0] ->Y = 0;for(int i = 1; i <= N; i++){Cd[i] = (Coordinate)malloc(sizeof(struct Coordinate));scanf("%d%d", &Cd[i] ->X, &Cd[i] ->Y);}return Cd;
}
PtrToAdjVNode Init_AdjVNode(Coordinate Cd)
{PtrToAdjVNode Node;Node = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));Node ->Cd = Cd;Node ->Brother = NULL;Node ->Child = NULL;return Node;
}bool Dict_E(int D, Coordinate start, Coordinate end)
{double Temp;Temp = sqrt(pow(start ->X - end ->X, 2) + pow(start ->Y - end ->Y, 2));if(Temp < D){return true;}else{return false;}
}
List Creat_Link(int N){List Link, rear;Link = (List)malloc(sizeof(struct Node));rear = Link;for(int i = 1; i <= N; i++){rear ->Next = Init_Link(i);rear = rear ->Next;}return Link;
}
List Init_Link(int data)
{List PtrL;PtrL = (List)malloc(sizeof(struct Node));PtrL ->data = data;PtrL ->Next = NULL;return PtrL;
}
void Delete_Link(List *Node)
{if(!(*Node)){return ;}List PtrL;PtrL = (*Node) ->Next;(*Node) ->Next = PtrL ->Next;free(PtrL);
}