04-树5 Root of AVL Tree (25分)
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted.
Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88
#include<stdio.h> #include<malloc.h> #define EH 0 //等高 #define RH -1 //右高 #define LH 1 //左高 typedef struct BSTNode *BSTree; void L_Rotate(BSTree &p); void R_Rotate(BSTree &p); void LeftBalance(BSTree &T); void RightBalance(BSTree &T); int InsertAVL(BSTree &T, int e, bool &taller); struct BSTNode { int data; int bf; //-1代表右高,1代表左高,0代表左右一样高 BSTree lchild; BSTree rchild; }; int main() { int n; scanf_s("%d", &n); int x; BSTree T=NULL; bool taller = false; for (int i = 0; i < n; i++) { scanf_s("%d", &x); InsertAVL(T, x, taller); } printf("%d ", T->data); return 0; } //右旋 void R_Rotate(BSTree &p) { BSTree lc; lc = p->lchild; //lc指向p的左子树的根结点 p->lchild = lc->rchild; //p的左子树接lc的右子树 lc->rchild = p; //lc的右子树接p p = lc; //p指向新的根结点 } //左旋 void L_Rotate(BSTree &p) { BSTree rc = p->rchild; //rc指向p的右子树的根结点 p->rchild = rc->lchild; //p的右子树接rc的左子树 rc->lchild = p; //rc的左子树接为p p = rc; //p指向新的根结点 } int InsertAVL(BSTree &T, int e, bool &taller) { //若在平衡的二叉搜索树T中不存在和e相同的结点则插入一个新结点,返回1,否则返回0 //若因插入使二叉搜索树失去平衡,则做平衡旋转处理,bool类型判断T是否长高 if (!T){//插入新结点,树长高,taller置为True T = (BSTree)malloc(sizeof(BSTNode)); T->data = e; T->lchild = T->rchild = NULL; T->bf = EH; taller = true; } else { if (e == T->data) //存在和e相同的结点不插入 { taller = false; return 0; } if (e < T->data) //应在T的左子树中进行搜索 { if (!InsertAVL(T->lchild, e, taller)) //返回值为0说明左子树中存在相同的结点,则直接return 0; return 0; if (taller) //如果树长高了,判断是否需要平衡 { switch (T->bf) //检查T的平衡因子 { case LH: //原来左子树比右子数高,又插入在左子树中,需要做平衡 LeftBalance(T); taller = false; break; case EH: T->bf = LH; taller = true; break; case RH: T->bf = EH; taller = false; break; } } } else //在T的右子树种进行搜索 { if (!InsertAVL(T->rchild, e, taller)) //返回值为0,说明右子树种存在相同的结点,不用插入 return 0; if (taller) { switch (T->bf) { case LH: T->bf = EH; taller = false; break; case EH: T->bf = RH; taller = true; break; case RH: RightBalance(T); taller = false; break; } } } } return 1; } void LeftBalance(BSTree &T) { //对以T为根结点的二叉树做左平衡旋转,结束后,指针T指向新的根结点 BSTree lc = T->lchild; switch (lc->bf) //检查T的左子树的平衡因子 { case LH: //如果左边高,则做右旋操作 T->bf = lc->bf = EH; //先修改平衡因子,右旋后,平衡因子置为EH R_Rotate(T); break; case RH: //如果右高,新结点插在T的左子树的右子树上,应做左右双旋 BSTree rd = lc->rchild; switch (rd->bf) //按照三种情况修改,T和lc的平衡因子 { case LH:lc->bf = EH; T->bf = RH; break; case EH:lc->bf = T->bf = EH; break; case RH:T->bf = EH; lc->bf = LH; break; } rd->bf = EH; //修改rd的平衡因子 L_Rotate(T->lchild); //对T的左子树进行左旋,旋转之后T的左孩子变为rd; R_Rotate(T); //然后对T进行右旋操作 break; } } void RightBalance(BSTree &T) { BSTree rc = T->rchild; //rc指向T的右子树 switch (rc->bf) { case RH: //插入在T的右子树的右子树上,应进行右旋操作 T->bf = rc->bf = EH;//先修改T和T的右子树的平衡因子 L_Rotate(T); break; case LH: //插入在T的右子树的左子树上,应进行右左双选操作 BSTree ld = rc->lchild; switch (ld->bf) { case LH:T->bf = EH; rc->bf = RH; break; case EH:T->bf = rc->bf = EH; break; case RH:T->bf = LH; rc->bf = EH; break; } ld->bf = EH; R_Rotate(T->rchild); //对T的右子树进行右旋,旋转后T的右子树的根结点变成ld L_Rotate(T); //然后对T进行左旋 break; } }
/*分析:
完全二叉搜索树,满足二叉搜索树的性质也满足完全二叉树的性质,画图可以知道,右边的值都比左边的大
可以先排个序,每个根结点的值排的位置都是左子树的个数,加上他左边的结点的个数.
#include<stdio.h> #include<math.h> #include<stdlib.h> #define Maxsize 1000 typedef struct TNode *BSTree; int a[1000]; struct TNode { int data; BSTree left; BSTree right; }; //队列的顺序存储 struct QNode { BSTree *bst; int front, rear; int maxsize; }; typedef struct QNode *Queue; Queue CreateQueue() { Queue Q = (Queue)malloc(sizeof(struct QNode)); Q->bst = (BSTree *)malloc(Maxsize*sizeof(struct TNode)); Q->front = Q->rear = 0; Q->maxsize = Maxsize; return Q; } int IsEmpty(Queue Q) { if (Q->front == Q->rear) return 1; else return 0; } //选择排序 void sort(int a[], int n) { for (int i = 0; i<n; i++) { for (int j = i + 1; j<n; j++) { if (a[i]>a[j]) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } } //求左子树结点的个数 int LeftNum(int n) { int k=0;// n个结点的树的层数 int m=1; //m-1表示k层满二叉树的结点个数 int p;//表示左子树结点的个数 while (m < n + 1) { m = 2 * m; k++; } if (m - 1 - (int)pow(2.0, k - 2) <= n) //左子树是满的 { p = (int)(pow(2.0, k - 1)) - 1; } else p = n - (int)pow(2.0, k - 2); return p; } BSTree Insert(int left, int n, BSTree T); void preOrderTravasel(BSTree T); void LevelTravasel(BSTree T); int main() { int n; scanf("%d", &n); for (int i = 0; i<n; i++) { scanf("%d", &a[i]); } //从小到大排序 sort(a, n); BSTree T=NULL; T=Insert(0, n,T); //preOrderTravasel(T); LevelTravasel(T); printf(" "); return 0; } void preOrderTravasel(BSTree T) { if (T != NULL) { printf("%d ", T->data); preOrderTravasel(T->left); preOrderTravasel(T->right); } } BSTree Insert(int left, int n, BSTree T) { if (n == 0) return NULL; T = (BSTree)malloc(sizeof(struct TNode)); int p = LeftNum(n); //左子树的个数 int m = n - p-1; //右子树的个数 T->data = a[p + left]; T->left = Insert(left, p, T->left); T->right = Insert(left + p + 1, m, T->right); return T; } void LevelTravasel(BSTree T) { Queue Q = CreateQueue(); Q->bst[Q->rear++] = T; int i = 0; while (IsEmpty(Q) == 0) { T = Q->bst[Q->front++]; if (i++ == 0) printf("%d", T->data); else printf(" %d", T->data); if (T->left != NULL) { Q->bst[Q->rear++] = T->left; } if (T->right != NULL) { Q->bst[Q->rear++] = T->right; } } }
Sample Input:
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11#include<stdio.h> #include<malloc.h> #include<string.h>
//分析:
//判断是否是最优解,其实就是判断wpl是否最小
//加上没有二义性,需要是前缀码
//算法思路:根据输入的,建立一个哈夫曼树,寻找两个最小的值,然后插入需要借助堆,然后求出最小的wpl.判断输入的每一组数据是否是前缀码和wpl最小
int value[256]; //哈夫曼树的定义 typedef struct TreeNode *HuffmanTree; typedef struct TreeNode { int weight; char data; HuffmanTree left, right; }Node; //最小堆 typedef struct TNode { HuffmanTree *data; int size; }*MinHeap; void Insert(int n, HuffmanTree T, MinHeap H); //最小堆插入 HuffmanTree Delete(MinHeap H); //最小堆删除 HuffmanTree BuildHuffman(MinHeap H); //建一个哈夫曼树 int Judge(int n, int totalspace); //判断是否是最右键 int WPL(HuffmanTree T, int Depth); //求wpl int main() { MinHeap H = (MinHeap)malloc(sizeof(struct TNode)); H->data = (HuffmanTree *)malloc(1001 * sizeof(HuffmanTree)); H->size = 0; //哨兵 HuffmanTree a = (HuffmanTree)malloc(sizeof(struct TreeNode)); a->weight = -1000; H->data[0] = a; int n; scanf_s("%d ", &n); //生成一个最小堆 for (int i = 0; i<n; i++) { Insert(1, NULL, H); } //建一个哈夫曼树 HuffmanTree T = BuildHuffman(H); //计算哈夫曼树形成的哈夫曼编码的最小wpl int Space = WPL(T,0); int m; scanf_s("%d", &m); getchar(); for (int i = 0; i<m; i++) { int sum; //输入的编码的wpl和最优的比较 sum=Judge(n,Space); if (sum == Space) printf("Yes "); else printf("No "); } } //最小堆的插入 void Insert(int n, HuffmanTree T, MinHeap H) { if (n == 1){ //当n=1时,是输入,建一个最小堆 char c; int weight; scanf_s("%c %d", &c, 1, &weight); int index = c; //将字母的权重存起来 value[index] = weight; getchar(); T = (Node *)malloc(sizeof(struct TreeNode)); T->weight = weight; T->data = c; T->left = NULL; T->right = NULL; int i = ++H->size; for (; H->data[i / 2]->weight>weight; i /= 2) { //向上过滤 H->data[i] = H->data[i / 2]; } //将T插入 H->data[i] = T; } else if (n == 2){ //n=2是插入一个结点 int i = ++H->size; for (; H->data[i / 2]->weight>T->weight; i /= 2){ H->data[i] = H->data[i / 2]; } H->data[i] = T; } } int WPL(HuffmanTree T, int Depth) { /* 整棵树的WPL */ if (!T->left && !T->left) { return Depth*T->weight; } else return WPL(T->left, Depth + 1) + WPL(T->right, Depth + 1); } //删除最小堆的堆顶元素 HuffmanTree Delete(MinHeap H) { HuffmanTree min = H->data[1]; //保存最后一个元素 int temp = H->size--; int child, parent; parent = 1; for (; parent * 2 <= H->size; parent = child) { //向下过滤,寻找要插入的位置 child = parent * 2; //找左右小的 if (child != H->size&&H->data[child + 1]->weight < H->data[child]->weight) { child++; } if (H->data[child]->weight >= H->data[temp]->weight) break; else { H->data[parent] = H->data[child]; } } //插入最后一个元素 H->data[parent] = H->data[temp]; return min; } //判断是否是最优解 int Judge(int n, int totalspace) { char c; char a[63]; char **str = (char **)malloc(n * 63 * sizeof(char)); for (int i = 0; i < n; i++) { //给n个字符串开辟空间 str[i] = (char *)malloc(63 * sizeof(char)); } int sum = 0; for (int i = 0; i < n; i++) { scanf_s("%c", &c, 1); getchar(); a[i] = c; scanf_s("%s", str[i], 63); getchar(); } //计算wpl for (int i = 0; i < n; i++) { sum += value[a[i]] * strlen(str[i]); } if (totalspace != sum) return -1; //字符串按长度排序 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (strlen(str[i])>strlen(str[j])) { char *p = str[i]; str[i] = str[j]; str[j] = p; char t = a[i]; a[i] = a[j]; a[j] = t; } } } //判断是否是前缀码 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int flag = 1; if (strlen(str[i]) == strlen(str[j])) { if (strcmp(str[i], str[j]) == 0) return -1; continue; } for (int k = 0; k < strlen(str[i]); k++) { if (str[i][k] != str[j][k]) { flag = 0; break; } } if (flag == 1) return -1; } } return sum; } //生成一个哈夫曼树 HuffmanTree BuildHuffman(MinHeap H) { int i; HuffmanTree T; int size = H->size; if (H->size == 1) { T = (HuffmanTree)malloc(sizeof(struct TreeNode)); T->weight = H->data[1]->weight; T->left = (HuffmanTree)malloc(sizeof(struct TreeNode)); T->left->weight = H->data[1]->weight; T->right = NULL; T->left->left = NULL; T->left->right = NULL; return T; } for (i = 1; i<size; i++) { //直到,堆中只有一个元素 T = (HuffmanTree)malloc(sizeof(struct TreeNode)); //取出两个最小的值 T->left = Delete(H); T->right = Delete(H); //加起来后,插进去 T->weight = T->left->weight + T->right->weight; Insert(2, T, H); } //取出堆顶元素 T = Delete(H); return T;
}
Sample Input 1:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
Sample Output 1:
no
no
yes
There are 2 components.Sample Input 2:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S
Sample Output 2:
no
no
yes
yes
The network is connected.#include<stdio.h> #include<malloc.h> #define MAXN 1000 /* 集合最大元素个数 */ typedef int ElementType; /* 默认元素可以用非负整数表示 */ typedef int SetName; /* 默认用根结点的下标作为集合名称 */ typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */ void Union(SetType S, SetName Root1, SetName Root2) { //按秩归并 //把元素少的集合连在元素多的上,可以降低树的高度 if (S[Root2] > S[Root1]) { S[Root1] += S[Root2]; S[Root2] = Root1; } else if (S[Root1] > S[Root2]) { S[Root2] += S[Root1]; S[Root1] = Root2; } } SetName Find(SetType S, ElementType X) { /* 默认集合元素全部初始化为-1 */ if (S[X] < 0) /* 找到集合的根 */ return X; else return S[X] = Find(S, S[X]); /* 路径压缩 */ //也是吧每一个路径上的元素,都直接连上根结点上,这样树的高度就降低了 } void Initial(SetType S, int n); //将集合中的每一个结点的parent置为-1 void Input_connection(SetType S); void Check_connection(SetType S); void Check_network(SetType S, int n); int main() { SetType S; int n; char in; //初始化集合 scanf_s("%d",&n); Initial(S, n); do{ scanf_s("%c", &in); switch (in){ case 'I':Input_connection(S); break; case 'C':Check_connection(S); break; case 'S':Check_network(S, n); } } while (in!='S'); return 0; } void Initial(SetType S, int n) { for (int i = 0; i < n; i++) { S[i]=-1; } } void Input_connection(SetType S) { int u, v; int root1, root2; scanf_s("%d %d ", &u, &v); //输入两个元素,然后找到,这两个元素的各自的集合,进行合并 root1 = Find(S, u - 1); root2 = Find(S, v - 1); Union(S, root1, root2); } void Check_connection(SetType S) { //检查两个元素是否在同一个集合中 int u, v; int root1, root2; scanf_s("%d %d ", &u, &v); //查找两个元素的根,是否是同一个结点 root1 = Find(S, u - 1); root2 = Find(S, v - 1); if (root1 == root2) printf("yes "); else printf("no "); } void Check_network(SetType S, int n) { //判断所有元素是否在同一个集合上 //小于0的只有一个,即只有一个集合,小于0的多个就有多个集合 int i,counter = 0; for (i = 0; i < n; i++) { if (S[i] < 0) counter++; } if (counter == 1) printf("The network is connected. "); else printf("There are %d components. ", counter); }
#include<stdio.h> //最小堆 int MinH[1001]; //size表示当前的最后一个结点的位置 int size = 0; void Insert(int x); void LuJin(int index); int main() { MinH[0] = -10001; int n, m; scanf_s("%d %d", &n, &m); for (int i = 0; i < n; i++) { int x; scanf_s("%d", &x); Insert(x); } for (int i = 0; i < m; i++) { int index; scanf_s("%d", &index); LuJin(index); } } //插入 void Insert(int x) { //要插入最后一个元素的位置 int i = ++size; for (; MinH[i / 2] > x; i /= 2) { //一直向上找 MinH[i] = MinH[i / 2]; } //找到后插入 MinH[i] = x; } void LuJin(int index) { int root = index; for (; root != 0; root /= 2) { if (root == index) printf("%d", MinH[root]); else printf(" %d", MinH[root]); } printf(" "); }
#include<stdio.h> #include<malloc.h>
//采用邻接表来表示图
/*算法思路:
先通过邻接表建一个图,建图时,需主要,题目要求从小到大,
故,每个链表都需要升序来排,不能直接头插了
然后先深度优先遍历,不连通的话,还需要一个for循环,
保证每个结点都被访问过,类似树的先序遍历
然后是广度优先遍历,类似树的层次遍历,需要队列*/
typedef struct node *List; typedef struct node *Node; struct node{ int V;//在数组中的下标 int weight; Node next; }; typedef struct VNode *PtrVNode; typedef struct VNode{ List firstEdge; }AdjList[1000]; AdjList G; int Nv; int Ne; int Visited[1000]; void visit(int Vertex) { printf("%d ", Vertex); } //定义队列 typedef struct queue{ int data[1000]; int front; int rear; int maxsize; }*Queue; Queue CreateQueue() { Queue Q = (Queue)malloc(sizeof(struct queue)); Q->front = Q->rear = 0; Q->maxsize = 1000; return Q; } void addQ(Queue Q, int x) { Q->data[Q->rear++] = x; } int DeleteQ(Queue Q) { return Q->data[Q->front++]; } int IsEmpty(Queue Q) { if (Q->front == Q->rear) return 1; else return 0; } void DFS(int V); void BFS(int V); int main() { scanf_s("%d %d", &Nv, &Ne); //初始化0条边,Nv个结点的图 for (int i = 0; i < Nv; i++) { G[i].firstEdge = NULL; } //插入Ne条边 int v1, v2, weight = 1; Node p; for (int i = 0; i < Ne; i++) { scanf_s("%d %d", &v1, &v2, &weight); //将v2插入到v1的链表中 Node NewNode = (Node)malloc(sizeof(struct node)); NewNode->V = v2; NewNode->weight = weight; if (G[v1].firstEdge == NULL) { NewNode->next = G[v1].firstEdge; G[v1].firstEdge = NewNode; } else{ p = G[v1].firstEdge; //链表升序 //寻找要插入的位置 if (v2 < p->V) { NewNode->next = G[v1].firstEdge; G[v1].firstEdge = NewNode; } else{ while (p->next != NULL&&v2 > p->next->V) p = p->next; //插入 NewNode->next = p->next; p->next = NewNode; } } //无向图,还需将v1插入到v2中 NewNode = (Node)malloc(sizeof(struct node)); NewNode->V = v1; NewNode->weight = weight; if (G[v2].firstEdge == NULL) { NewNode->next = G[v2].firstEdge; G[v2].firstEdge = NewNode; } else{ p = G[v2].firstEdge; //链表升序 //寻找要插入的位置 if (v1 < p->V) { NewNode->next = G[v2].firstEdge; G[v2].firstEdge = NewNode; } else{ while (p->next != NULL&&v1 > p->next->V) p = p->next; //插入 NewNode->next = p->next; p->next = NewNode; } } } //使用DFS和BFS遍历 for (int v = 0; v < Nv; v++) { int i = 0; if (!Visited[v]) { printf("{ "); DFS(v); i++; } if (i != 0) printf("} "); }
//遍历完后,需要将visited[]重新置为0 for (int v = 0; v < Nv; v++) { Visited[v] = 0; } for (int v = 0; v < Nv; v++) { int i = 0; if (!Visited[v]) { printf("{ "); BFS(v); i++; } if (i != 0) printf("} "); } } void DFS(int V) {
//先访问 visit(V); Visited[V] = 1; for (Node v = G[V].firstEdge; v != NULL; v = v->next) { if (!Visited[v->V]) //如果没有被访问,就访问 DFS(v->V); } } void BFS(int V) { Queue Q = CreateQueue(); visit(V); Visited[V] = 1; addQ(Q, V); Node p; while (!IsEmpty(Q)) { int v = DeleteQ(Q); for (p = G[v].firstEdge; p != NULL; p = p->next) { if (Visited[p->V] != 1){ visit(p->V); Visited[p->V] = 1; addQ(Q, p->V); } } } }
#include<stdio.h> #include<malloc.h> #include<math.h>
//算法思路:
//用坐标表示鳄鱼的位置
//两点距离小于跳的距离就表示两点相连
//第一跳的距离要加上岛的半径
//存在图中,然后dfs遍历图
typedef struct Location { double x; double y; }location,Node[101]; int G[101][101]; int Ne; int Nv; //判断是否能上岸 int flag = 0; int visited[102]; double Distance2(location a); //计算与岸上的距离 double Distance(location a, location b); //计算两点距离 void DFS(int v); int main() { double jump; Node node; node[0].x = 0; node[0].y = 0; scanf_s("%d %lf", &Nv,&jump); double distance; double distance2; for (int i = 1; i <= Nv; i++) { scanf_s("%lf %lf", &node[i].x, &node[i].y); } int flag1 = 0; for (int i = 0; i < Nv + 1; i++) { distance = Distance(node[0], node[i]) - 15; if (distance <= jump) { G[0][i] = 1; flag1 = 1; } } if (flag1 != 1) { printf("No "); return 0; } //插入边 for (int i = 1; i < Nv+1; i++) { //先算该结点是否与岸上相连 distance2= Distance2(node[i]); if (G[i][Nv+1] != 1 && distance2 <= jump) { G[i][Nv+1] = 1; } for (int j = i + 1; j < Nv+1; j++) { distance = Distance(node[i], node[j]); if (distance <= jump&&G[i][j]!=1) { G[i][j] = 1; G[j][i] = 1; } } } //判断有没有结点能上岸, flag1 = 0; for (int i = 0; i < Nv + 1; i++) { if (G[i][Nv + 1] == 1) { flag1 = 1; break; } } //没有结点与岸相连 if (flag1 == 0) { printf("No "); return 0; } DFS(0); if (flag == 1) printf("Yes "); else printf("No "); } double Distance(location a,location b) { double distance; distance = sqrt(double(a.x - b.x)*(a.x - b.x) + double(a.y - b.y)*(a.y - b.y)); return distance; } double Distance2(location a) { double Xdistance; double Ydistance; if (a.x >= 0){ Xdistance = 50 - a.x; } else Xdistance = a.x + 50; if (a.y >= 0){ Ydistance = 50 - a.y; } else Ydistance = a.y + 50; return Xdistance < Ydistance ? Xdistance : Ydistance; } void DFS(int v) { //判断是否与岸相连 visited[v]=1; if (v == Nv + 1) { flag = 1; return; } else { for (int i = 0; i < Nv + 2; i++) { if (G[v][i] == 1&&visited[i]!=1) { DFS(i); } } } }
Sample Input 1:
17 15
10 -21
10 21
-40 10
30 -50
20 40
35 10
0 -10
-25 22
40 -40
-30 30
-10 22
0 11
25 21
25 10
10 10
10 35
-30 10
Sample Output 1:
4
0 11
10 21
10 35
Sample Input 2:
4 13
-12 12
12 12
-12 -12
12 -12
Sample Output 2:
0#include<cstdio> #include<stdlib.h> #include<iostream> using namespace std; typedef struct Node *List; struct Node { int v;//在图中的数组下标 List next; double distance; }; typedef struct GNode { List FirstEdge; double x; double y; double distance; }GNode,Graph[102]; double Distance2(GNode a); //计算与岸上的距离 double Distance1(GNode a,GNode b); //计算两点距离 void BFS(int S,int n); int dist[102] = {0};//存储距离 int path[102] = { 0 }; //存储路径 int a[100] = { 0 }; Graph G; typedef struct position { double x; double y; }Position[100]; int main01() { int n, distance; cin >> n; cin >> distance; //原点和岸边 G[0].FirstEdge = NULL; G[0].x = 0; G[0].y = 0; G[n + 1].FirstEdge = NULL; dist[0] = 0; dist[n + 1] = -1; path[n + 1] = -1; //初始化图,输入坐标 for (int i = 1; i <= n; i++) { cin >> G[i].x >> G[i].y; G[i].FirstEdge = NULL; dist[i] =path[i]= -1; } int j = 0; //如果第一跳直接跳上岸 if (Distance2(G[0]) <= distance + 7.5) { cout << 1 << endl; return 0; } //先判断有没有第一跳 for (int i = 1; i <= n; i++) { if (Distance1(G[0], G[i]) <= distance + 7.5) { List NewNode = (List)malloc(sizeof(struct Node)); NewNode->v = i; NewNode->next = G[0].FirstEdge; G[i].distance = Distance1(G[0], G[i]); NewNode->distance = Distance1(G[0], G[i]); G[0].FirstEdge = NewNode; j++; } } if (j == 0) { cout << 0 << endl; return 0; } //将第一跳按距离排序从小到大 for (List p = G[0].FirstEdge; p != NULL; p = p->next) { for (List p1 = p->next; p1 != NULL; p1 = p1->next) { if (p->distance > p1->distance) { int t = p->v; p->v = p1->v; p1->v = t; double tmp = p->distance; p->distance = p1->distance; p1->distance = tmp; } } } //插入边 int k = 0; for (int i = 1; i <= n; i++) { if (Distance2(G[i]) <= distance) { List NewNode = (List)malloc(sizeof(struct Node)); NewNode->v = n+1; NewNode->next = G[i].FirstEdge; G[i].FirstEdge = NewNode; k++; } for (int j = i + 1; j <= n; j++) { if (Distance1(G[i], G[j]) <= distance) { List NewNode = (List)malloc(sizeof(struct Node)); NewNode->v = j; NewNode->next = G[i].FirstEdge; G[i].FirstEdge = NewNode; NewNode = (List)malloc(sizeof(struct Node)); NewNode->v = i; NewNode->next = G[j].FirstEdge; G[j].FirstEdge = NewNode; } } } //如果没有与岸相连的结点 if (k == 0) { cout << 0 << endl; return 0; } //遍历 BFS(0, n); int p = path[n + 1]; int f = 1; Position array; //逆转path输出路径 while (p != 0) { array[f - 1].x = G[p].x; array[f - 1].y = G[p].y; f++; p = path[p]; } cout << f << endl; for (int j = f - 2; j >= 0; j--) { cout << array[j].x << " " << array[j].y << endl; } return 0; } double Distance1(GNode a, GNode b) { double distance; distance = sqrt((double)(a.x - b.x)*(a.x - b.x) + (double)(a.y - b.y)*(a.y - b.y)); return distance; } double Distance2(GNode a) { double Xdistance; double Ydistance; if (a.x >= 0){ Xdistance = 50 - a.x; } else Xdistance = a.x + 50; if (a.y >= 0){ Ydistance = 50 - a.y; } else Ydistance = a.y + 50; return Xdistance < Ydistance ? Xdistance : Ydistance; } typedef struct Queue { int data[102]; int front; int rear; }Queue; void BFS(int S,int n) { Queue Q; int v; Q.front = Q.rear = 0; Q.data[Q.rear++] = S; while (Q.front != Q.rear) { v = Q.data[Q.front++]; for (List p = G[v].FirstEdge; p != NULL; p = p->next) { if (dist[p->v] == -1) { if (p->v == n + 1) { dist[p->v] = dist[v] + 1; path[p->v] = v; return; } else { dist[p->v] = dist[v] + 1; path[p->v] = v; Q.data[Q.rear++] = p->v; } } } } }