#include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX 150 struct ENode { int V1,V2; }; typedef struct ENode *bian; struct AdjVNode { int subscript; struct AdjVNode *next_subscript; }; typedef struct AdjVNode *spot; typedef struct headAdjVNode { int head_spot; spot next_spot; } H[MAX]; struct GNode { int Nv; int Ne; H G; }; typedef struct GNode *list; struct ey { int x,y; }; typedef struct ey eryu; eryu zoubiao[MAX]; int visit[MAX]; list creat(int sum); void gojian(list head,int num,int sum); void charu(list head,int left,int right); void bianli(list head,int now_spot,int num); int main() { int sum,num; scanf("%d%d",&sum,&num); list tu; tu=creat(sum); gojian(tu,num,sum); // for(int i=0;i<=sum;i++){ // printf("%d:",i); // for(spot tran=tu->G[i].next_spot;tran;tran=tran->next_subscript) // printf(" %d",tran->subscript); // printf("\n"); // } if(tu->G[0].next_spot==NULL) { printf("No\n"); }else if(num+7.5>=50){ printf("Yes\n"); } else { bianli(tu,0,num); printf("No\n"); } return 0; } list creat(int sum) { list head; head=(list)malloc(sizeof(struct GNode)); head->Nv=sum; head->Ne=0; for(int i=0; i<=sum; i++) { head->G[i].head_spot=i; visit[i]=0; head->G[i].next_spot=NULL; } return head; } void gojian(list head,int num,int sum) { zoubiao[0].x=0,zoubiao[0].y=0; for(int i=1; i<=sum; i++) scanf("%d%d",&zoubiao[i].x,&zoubiao[i].y); for(int i=1; i<=sum; i++) { int goudu=sqrt(pow(zoubiao[i].x,2)+pow(zoubiao[i].y,2)); if(goudu<=(7.5+num)) charu(head,0,i); } for(int i=1; i<sum; i++) { for(int j=i+1; j<=sum; j++) { if(sqrt(pow((zoubiao[i].x-zoubiao[j].x),2)+pow((zoubiao[i].y-zoubiao[j].y),2))<=num) charu(head,i,j); } } } //创建边 void charu(list head,int left,int right) { bian tran; spot spot_tran; spot_tran=(spot)malloc(sizeof(struct AdjVNode)); tran=(bian)malloc(sizeof(struct ENode)); tran->V1=left; tran->V2=right; spot_tran->subscript=right; spot_tran->next_subscript=head->G[left].next_spot; head->G[left].next_spot=spot_tran; spot_tran=(spot)malloc(sizeof(struct AdjVNode)); spot_tran->subscript=left; spot_tran->next_subscript=head->G[right].next_spot; head->G[right].next_spot=spot_tran; } void bianli(list head,int now_spot,int num) { if(50-abs(zoubiao[now_spot].x)<=num || 50-abs(zoubiao[now_spot].y)<=num){ printf("Yes\n"); exit(0); } visit[now_spot]=1; for(spot tran=head->G[now_spot].next_spot;tran;tran=tran->next_subscript){ if(visit[tran->subscript]==0) bianli(head,tran->subscript,num); } }
时间: 2024-03-11 16:46:22 浏览: 16
这是一段C语言代码,看起来是一个求解迷宫问题的程序。程序中使用了图论的相关知识,包括邻接表存储图、BFS遍历图等。程序的具体实现如下:
1. 定义了一个结构体ENode,表示边,其中包括两个顶点V1和V2;定义了一个指向ENode的指针类型bian。
2. 定义了一个结构体AdjVNode,表示邻接点,其中包括一个子节点subscript和指向下一个子节点的指针next_subscript;定义了一个指向AdjVNode的指针类型spot。
3. 定义了一个结构体headAdjVNode,表示邻接表,其中包括一个头节点head_spot和指向第一个邻接点的指针next_spot。
4. 定义了一个结构体GNode,表示图,其中包括图的顶点数Nv、边数Ne和图的邻接表G;定义了一个指向GNode的指针类型list。
5. 定义了一个结构体ey,表示坐标,其中包括x和y两个坐标值;定义了一个ey类型的数组zoubiao[MAX],用于存储迷宫中的坐标。
6. 定义了一个visit数组,用于记录每个顶点是否被访问过。
7. 定义了creat函数,用于创建图,其中包括初始化图的各个节点和邻接表。
8. 定义了gojian函数,用于将迷宫中的点按照一定规则连接起来,形成图。
9. 定义了charu函数,用于在图中插入一条边。
10. 定义了bianli函数,用于以BFS方式遍历图,查找从起点到终点的路径。
11. 在主函数中,先调用creat函数创建图,然后调用gojian函数将迷宫中的点连接起来,再调用bianli函数以BFS方式遍历图,查找从起点到终点的路径。如果找到了路径,则输出"Yes",否则输出"No"。
需要注意的是,代码中存在一些注释掉的部分(以"//"开头的行),这些部分可能是作者在调试程序时添加的,对程序的逻辑并没有影响。