欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

进阶实验6-3.4-拯救007(升级版)-编程题

程序员文章站 2022-06-07 20:47:53
...

进阶实验6-3.4-拯救007(升级版)-编程题

解题代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXN 100
#define SIDE 100
#define DIA 15
typedef enum { false, true } bool;
typedef struct Data *PtrToData;
struct Data {
	int x, y;
	int level;
	double Distance;
	int last;
}C[MAXN];
int B[MAXN],Q[MAXN];
int N, D, front = -1, rear = -1, LEVEL, LAST, TAIL;
void Initialization_Level(void);
void Solve_Distance(void);
int Cmp(const void *a, const void *b);
void Enqueue(int V, int index);
int Dequeue(void);
bool FirstJump(int index);
bool CanJumpToSide(int index);
int BFS(void);
bool CanJump(int index1, int index2);
void Print(int V);
bool IsEmpty(void);
void RePrint(int V, int L);
int main()
{
	int i, V, flag=0;
	scanf("%d %d", &N, &D);
	if (CanJumpToSide(-1)) flag = 1;
	for (i = 0; i < N; i++)
		scanf("%d %d", &C[i].x, &C[i].y);
	Initialization_Level();
	Solve_Distance();
	qsort(C, N, sizeof(struct Data), Cmp);
	LEVEL++;
	for (i = 0; i < N; i++)
		if (!B[i] && FirstJump(i)) {
			B[i] = 1;
			Enqueue(-1,i);
			TAIL = i;
		}
	LAST = TAIL;
	V = BFS();
	if (flag) printf("1");
	else if (V != -1) Print(V);
	else printf("0");
	return 0;
}
void Initialization_Level(void) {
	for (int i = 0; i < N; i++) {
		C[i].level = 0;
		C[i].last = -1;
	}
}
void Solve_Distance(void) {
	for (int i = 0; i < N; i++)
		C[i].Distance = sqrt(pow(C[i].x, 2) + pow(C[i].y, 2));
}
int Cmp(const void *a, const void *b) {
	return (int)(((PtrToData)a)->Distance - ((PtrToData)b)->Distance);
}
void Enqueue(int V, int index) {
	Q[++rear] = index;
	C[index].level = LEVEL;
	C[index].last = V;
}
int Dequeue(void) {
	return Q[++front];
}
bool FirstJump(int index) {
	if (C[index].Distance <= (double)DIA / 2 + D) return true;
	else return false;
}
bool CanJumpToSide(int index) {
	if (index == -1) {
		if ((double)DIA/2+D >= (double)SIDE / 2) return true;
		else return false;
	}
	else {
		int x = C[index].x;
		int y = C[index].y;
		if (x >= (double)SIDE / 2 - D || x <= D - (double)SIDE / 2 || y >= (double)SIDE / 2 - D || y <= D - (double)SIDE / 2) return true;
		else return false;
	}
}
int BFS(void) {
	int V, i;
	LEVEL++;
	while (!IsEmpty()) {
		V = Dequeue();
		if (CanJumpToSide(V)) return V;
		for(i=0;i<N;i++)
			if (!B[i]&&CanJump(V, i)) {
				B[i] = 1;
				Enqueue(V,i);
				TAIL = i;
			}
		if (V == LAST) {
			LAST = TAIL;
			LEVEL++;
		}
	}
	return -1;
}
bool CanJump(int index1,int index2) {
	int x1 = C[index1].x, y1 = C[index1].y;
	int x2 = C[index2].x, y2 = C[index2].y;
	double distance = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
	if (distance <= D) return true;
	else return false;
}
void Print(int V) {
	printf("%d", C[V].level + 1);
	RePrint(V, C[V].level);
}
bool IsEmpty(void) {
	if (front == rear) return true;
	else return false;
}
void RePrint(int V,int L) {
	if (!L) return;
	RePrint(C[V].last, L - 1);
	printf("\n%d %d", C[V].x, C[V].y);
}

测试结果

进阶实验6-3.4-拯救007(升级版)-编程题

问题整理

1.这题还挺复杂,复杂在最终的输出逻辑上,我通过在每个鳄鱼头上记下了他的上一个鳄鱼,来进行递归输出。
2.	错误1:Cmp辅助函数的指针格式转换。
	错误2:入队的同时赋给C[index].last值误写作C[rear].last。
	错误3:CanJumpToSide函数的判断条件中错写成y <= (double)SIDE / 2 - D。
	错误4:CanJump中错写为pow(y1 - y1, 2)。我都服了我自己,这些错误真无语。。
	错误5:在最后的RePrint函数中的RePrint(C[V].last, L - 1),注意第一个参数不是LEVEL。