进阶实验6-3.4-拯救007(升级版)-编程题
程序员文章站
2022-06-07 20:47:53
...
解题代码
#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);
}
测试结果
问题整理
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。