- 我不懂运营
-
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
//#include "Deque.h"
//#include "error.h"
#define ISLAND_DIAMETER 15 /* 小岛的直径 */
#define LAKE_BOUNDARY_X 50 /* 小岛到湖边的距离,在x轴上 */
#define LAKE_BOUNDARY_Y 50 /* 小岛到湖边的距离,在y轴上 */
#define INFINITY 10000 /* 可以跳的步数的最大值 */
typedef unsigned int Vertex;
typedef double Distance;
typedef struct GraphNodeRecord{
int X; /* x轴坐标 */
int Y; /* y轴坐标 */
unsigned int Step; /*跳至该点的步数 */
Vertex Path; /*记录上一个点 */
} GraphNode;
typedef GraphNode *Graph;
Graph GraphNew(int NodeNum);
void GraphDelete(Graph G);
/* 判断007是否能从起始处跳至该点(x, y) */
int CheckForStart(int x, int y, Distance d);
/* 判断007是否能从该点跳至河岸 */
int CheckForEnd(int x, int y, Distance d);
/* 判断007是否能从点i跳至点j */
int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d);
typedef unsigned int ElemType; /* 在本程序中ElemType指定为int */
/* 链表形式 */
typedef struct NodeRecord{
ElemType Element;
struct NodeRecord *Next; /* 指向下一个node */
} *Node;
typedef struct DequeRecord{
Node Front, Rear; /* 分别指向Deque的前后两个点 */
} *Deque;
Deque DequeNew();
void DequeDelete(Deque D);
void DequeClear(Deque D);
int IsEmpty(Deque D);
void Push(ElemType X, Deque D);
ElemType Pop(Deque D);
void Inject(ElemType X, Deque D);
#define CHECK(X) if(NULL == (X))Error("Out of space!!!")
void Error(const char *msg);
void Warning(const char *msg);
/******创建新的Graph******/
Graph GraphNew(int NodeNum)
{
Graph G;
int i;
if(NodeNum <= 0)return NULL;
G =(GraphNodeRecord *) malloc(NodeNum * sizeof(GraphNode)); /* 分配空间 */
CHECK(G);
for(i = 0; i < NodeNum; i++) /* 初始化 */
{
G[i].X = 0;
G[i].Y = 0;
G[i].Step = INFINITY;
G[i].Path = 0;
}
return G;
}
/******删除一个Graph)******/
void GraphDelete(Graph G)
{
if(G)free(G);
}
/*******判断007是否能从起始处跳至该点(x, y),步长是d******/
int CheckForStart(int x, int y, Distance d)
{
double t;
t = (ISLAND_DIAMETER + (d * 2.0));
return (x*x + y*y) <= t*t/4.0;
/* x^2 + y^2 <= (ISLAND_DIAMETER/2.0 + d)^2 */
}
/*******判断007是否能从该点跳至河岸,步长是d******/
int CheckForEnd(int x, int y, Distance d)
{
if(x < 0)x = -x; /* 取x的绝对值 */
if(y < 0)y = -y; /* 取y的绝对值 */
return (d >= LAKE_BOUNDARY_X - x) /* 由于湖是个正方形,只需检查这两个距离*/
|| (d >= LAKE_BOUNDARY_Y - y);
}
/*******判断007是否能从点i跳至点j,步长是d******/
int CheckForConnect(Graph g, Vertex i, Vertex j, Distance d)
{
int x, y;
x = g[i].X - g[j].X;
y = g[i].Y - g[j].Y;
return x*x + y*y <= d*d;
}
/******创建新的Deque******/
Deque DequeNew()
{
Deque D;
D =(DequeRecord *) malloc(sizeof(struct DequeRecord));
CHECK(D);
D->Front = D->Rear =(NodeRecord *) malloc(sizeof(struct NodeRecord)); /* 空的头 */
CHECK(D->Front);
D->Front->Element = 0; /* 初始化 */
D->Rear->Next = NULL;
return D;
}
/******删除Deque******/
void DequeDelete(Deque D)
{
if(D)
{
while(D->Front)
{
D->Rear = D->Front->Next;
free(D->Front);
D->Front = D->Rear;
}
free(D);
}
}
/******DequeClear删除所有的节点除了头节点******/
void DequeClear(Deque D)
{
if(D)
{
while(D->Front->Next) /* 删除第一个节点 */
{
D->Rear = D->Front->Next->Next;
free(D->Front->Next);
D->Front->Next = D->Rear;
}
D->Rear = D->Front;
}
}
/******判断Deque是否为空******/
int IsEmpty(Deque D)
{
return D->Front == D->Rear;
}
/******将X元素压占到D中******/
void Push(ElemType X, Deque D)
{
Node NewNode;
NewNode =(NodeRecord *) malloc(sizeof(struct NodeRecord)); /* 建立新的节点 */
CHECK(NewNode);
NewNode->Element = X;
NewNode->Next = D->Front->Next;
if(D->Front == D->Rear) /* 如果D为空 */
D->Rear = NewNode;
D->Front->Next = NewNode; /* 压栈 */
}
/******将第一个元素出栈******/
ElemType Pop(Deque D)
{
Node Temp;
ElemType Item;
if(D->Front == D->Rear)
{
Error("Deque is empty");
return 0;
}
else
{
Temp = D->Front->Next; /* 得到第一个元素 */
D->Front->Next = Temp->Next; /* 重置第一个元素 */
if(Temp == D->Rear) /* 如果只有一个元素 */
D->Rear = D->Front; /* 将D置空 */
Item = Temp->Element;
free(Temp);
return Item;
}
}
/******插入元素X至D末尾******/
void Inject(ElemType X, Deque D)
{
Node NewNode;
NewNode =(NodeRecord *) malloc(sizeof(struct NodeRecord)); /* 创建新节点 */
CHECK(NewNode);
NewNode->Element = X;
NewNode->Next = NULL;
D->Rear->Next = NewNode;
D->Rear = NewNode;
}
/******打印错误信息,并退出程序******/
void Error(const char *msg)
{
if(NULL != msg)
fprintf(stderr,"%s ",msg);
exit(-1);
}
/******打印警告信息,但并不退出程序******/
void Warning(const char *msg)
{
if(NULL != msg)
fprintf(stderr,"%s ",msg);
}
;
/******读入一个case返回一个Graph,*Bank 记录最短到达河岸的路径******/
Graph read_case(FILE *InFile, int num, Vertex* Bank, Deque D)
{
Graph G = NULL;
Distance JamesJump;
Vertex V;
int x, y;
int i, Times;
*Bank = 0;
fscanf(InFile, "%lf", &JamesJump);
if(CheckForEnd(0, 0, JamesJump + ISLAND_DIAMETER/2.0))
{
for(i = 0; i < (num << 1); i++) /*一步便跳出的情况 */
fscanf(InFile, "%d", &x);
*Bank = 1;
}
else if(num > 0) /* 007必须经过鳄鱼头上的情况 */
{
num += 2;
G = GraphNew(num);
for(i = 2; i < num; i++) /* 第三个node开始是鳄鱼 */
{
fscanf(InFile, "%d", &x);
fscanf(InFile, "%d", &y);
G[i].X = x;
G[i].Y = y;
if(CheckForStart(x, y, JamesJump)) /*判断是否能跳上该点*/
{
G[i].Path = 1; /*007可以跳到 */
G[i].Step = 1; /* 一步 */
if(CheckForEnd(x, y, JamesJump)) /* 判断该点是否能跳出 */
{
*Bank = i; /* 007可以跳出 */
Times = (num - i - 1) << 1;
for(i = 0; i < Times; i++) /* 不必检验其他鳄鱼 */
fscanf(InFile, "%d", &y);
DequeClear(D);
break;
}
else
Inject(i, D); /* 插入该点,并开始下一个检测 */
}
}
while(!IsEmpty(D)) /*只经过一个鳄鱼无法跳出,必须还要跳到其它鳄鱼的情况 */
{
V = Pop(D);
for(i = 2; i < num; i++) /* 从这只鳄鱼跳到其他各个鳄鱼 */
{
if((G[i].Step > G[V].Step + 1)
&& CheckForConnect(G, V, i, JamesJump))
{
G[i].Path = V;
G[i].Step = G[V].Step + 1;
if((G[i].Step < G[*Bank].Step)
&& CheckForEnd(G[i].X, G[i].Y, JamesJump))
*Bank = i;
else
Inject(i, D);
}
}
}
}
return G;
}
/******写出结果,即最短路径******/
void write_result(FILE *OutFile, Vertex Bank, Graph G, Deque D)
{
unsigned int Times, i;
Vertex V;
switch(Bank){
case 0: /* 007无法跳出 */
fprintf(OutFile, "%d ", -1);
break;
case 1: /* 007可以直接跳出 */
fprintf(OutFile, "%d ", 1);
break;
default:
Times = G[Bank].Step + 1; /* 跳的步数 */
while(Bank != 1) /* 跟踪路径 */
{
Push(Bank, D);
Bank = G[Bank].Path;
}
fprintf(OutFile, "%d ", Times); /* 输出 */
for(i = 1; i < Times; i++)
{
V = Pop(D);
fprintf(OutFile, "%d ", G[V].X);
fprintf(OutFile, "%d ", G[V].Y);
}
}
}
int main(int argc, char *argv[])
{
FILE *in, *out;
Deque D;
int VertexNum;
Graph G = NULL;
Vertex Bank = 0;
in = fopen("input.txt", "r");
if(NULL == in)
{
fprintf(stderr, "Can not open input.txt");
exit(-1);
}
out = fopen("output.txt", "w");
if(NULL == out)
{
fprintf(stderr, "Can not open output.txt");
fclose(in);
exit(-1);
}
D = DequeNew();
while((EOF != fscanf(in, "%d", &VertexNum)) && (0 <= VertexNum))
{
G = read_case(in, VertexNum, &Bank, D); /* 读文件直到结尾 */
write_result(out, Bank, G, D);
if(G)
GraphDelete(G);
}
fclose(in);
fclose(out);
DequeDelete(D);
return 0;
}
这是你那个网址里的代码调试通过了,也得到了如例子里的结果。你自己试试吧。
要说明的是请把input.txt和程序放在里一文件夹下再运行程序