#include<stdio.h> #include<stdlib.h> #include<math.h> #define r 15/2 typedef int Vertex; typedef int WeightType; typedef struct GNode* MGraph; int queue[2502] = {-1}; int dist[2502] = {-1}; int path[2502] = {-1}; struct GNode { Vertex x, y; }; int coordienum, jumpdist; void Save007(MGraph Graph); int Unweighted(MGraph S); int IsSafe(MGraph human, int i); int FirstJump(struct GNode Graph); int Jump(struct GNode Graph1, struct GNode Graph2); MGraph CreateCoordieLoacation(); int main() { //创建湖泊和鳄鱼的位置 //分析如何去岸边 for (int i = 0; i < 2502; i++) { path[i] = -1; dist[i] = -1; } MGraph Graph = NULL; Save007(Graph); while (1); } void Save007(MGraph Graph) //拯救的过程 { int judge; Graph = CreateCoordieLoacation(); judge=Unweighted(Graph); if (judge != 0) { dist[judge] += 3; printf("%d\n", dist[judge]); while (path[judge] != judge) { printf("%d %d\n", Graph[judge].x, Graph[judge].y); judge = path[judge]; } printf("%d %d\n", Graph[judge].x, Graph[judge].y); } else { printf("0\n"); } } int Unweighted(MGraph S) //找到最短路径 { int tail=-1, front=-1; int V,answer=0; for (int i = 0; i < coordienum; i++) { if (FirstJump(S[i])) { queue[++tail] = i; } } while (front < tail) { V = queue[++front]; if (IsSafe(S, V)) return V; else for (int i = 0; i < coordienum; i++) { if(Jump(S[V],S[i])) if (dist[i] == -1) { dist[i] = dist[V] + 1; path[i] = V; queue[++tail] = i; } } } return 0; } int IsSafe(MGraph human, int i) //是否获救 { if (50-abs(human[i].x) <= jumpdist || 50-abs(human[i].y) <= jumpdist) return 1; return 0; } int FirstJump(struct GNode Graph) //第一跳 { if (sqrt(pow(Graph.x, 2) + pow(Graph.y, 2)) < jumpdist + r) return 1; return 0; } int Jump(struct GNode Graph1, struct GNode Graph2) //判断是否可以跳,也就是判断是否为临节点 { if (sqrt(pow(Graph1.x - Graph2.x, 2) + pow(Graph1.y - Graph2.y, 2)) < jumpdist) return 1; return 0; } MGraph CreateCoordieLoacation() { scanf_s("%d%d", &coordienum, &jumpdist); MGraph Graph = (MGraph)malloc(sizeof(struct GNode)*coordienum); for (int i = 0; i < coordienum; i++) { scanf_s("%d%d", &Graph[i].x, &Graph[i].y); } return Graph; }
注:放在PTA上不会对哦,因为我没有用堆栈输出,所以会造成与PTA题目上相反的答案,所以你们需要制作一个堆栈在来输出