关于数据结构Mooc后的每一道答案
基本我都已经给出了详解
希望能对大家有所帮助
收藏一下也是方便大家查找吧
希望大家一起进步！
浙大Mooc数据结构的解题集
原题题目
关于此题的闲谈
也没什么闲谈 就是做题 看视频 做题 积累 找Bug
现在也不知道为什么 做出来题之后的快乐很短暂
跟刚开始出来做的那种快乐持续感 也太大了
每次做完 看到答案是对的 现在也就开心个10秒
然后就恢复平静hhh 可能是有点重复了 但是坚持
再坚持一下 也许就能走到一个地方很多乐趣了
关于思路
1、搜索选择算法
很明显这道题是需要DFS的
因为我们的目标就是到达边缘 所以DFS比BFS广度更好一点
int DepthFirstSearch(Point Mypoint,int number)
{
//answer用来判断是否有机会到岸//如果返回了一次1 即刻退出程序并返回1//如果一直都是0 则不改变原先的值int i,answer = 0;Visit[number] = 1;//每一次先检验是否可以到岸if(IsSafe(Mypoint))return 1;else{
for(i=1;i<=CrocodileNumbers;i++){
if(!Visit[i] && Distance(Points[i],Mypoint,JumpAbility)){
answer = DepthFirstSearch(Points[i],i);//只要返回了一次值为1 就说明可以成功逃生if(answer)break;}}}return answer;
}
2、判断跳跃成功、是否能够离岸
**
每当我们判断是否能跳上去时
能跳上去就是距离小于我们JumpLength噻
每次都进行计算那太麻烦了
所以这个时候我们就需要一个函数Distance来判断是否可以跳上去
//检测距离函数
int Distance(Point p1,Point p2,double JumpLength)
{
//第一次的FirstJump和之后的JumpAbility变量都可以使用这个函数if(JumpLength >= sqrt(pow(p1.x - p2.x,2)+ pow(p1.y - p2.y,2)))return 1;elsereturn 0;
}//检测是否安全函数
int IsSafe(Point Mypoint)
{
if(fabs(Mypoint.x+50)<=JumpAbility || fabs(Mypoint.x-50)<=JumpAbility || fabs(Mypoint.y+50)<=JumpAbility || fabs(Mypoint.y -50)<=JumpAbility)return 1;elsereturn 0;
}
代码实现
尽管代码看起来很长 但是主要部分就那么点
主要我没有缩进格式省行数 就那么多
#include <stdio.h>
#include <math.h>
#define MAX 110
typedef int vertex;
typedef struct
{
int x;int y;
} Point;//JumoAbility设置为全局变量
//方便Distance函数使用
double JumpAbility;
int CrocodileNumbers;
int Visit[MAX];//记录所有的点位数 这里我没有使用邻接矩形
//并且这里也包含了"我"的位置 0,0
Point Points[MAX];void InsertCrocodiles();
void InitVisit();
int Distance(Point p1,Point p2,double JumpLength);
int IsSafe(Point Mypoint);
int DepthFirstSearch(Point Mypoint,int number);//插入鳄鱼的位置
void InsertCrocodiles()
{
int i;for(i=1;i<=CrocodileNumbers;i++)scanf("%d%*c%d",&Points[i].x,&Points[i].y);return;
}//初始化Visit
void InitVisit()
{
int i;for(i=0;i<=MAX;i++)Visit[i] = 0;return;
}//计算距离函数
int Distance(Point p1,Point p2,double JumpLength)
{
if(JumpLength >= sqrt(pow(p1.x - p2.x,2)+ pow(p1.y - p2.y,2)))return 1;elsereturn 0;
}//判断能否离岸函数
//就是根据题意写的 很简单
int IsSafe(Point Mypoint)
{
if(fabs(Mypoint.x+50)<=JumpAbility || fabs(Mypoint.x-50)<=JumpAbility || fabs(Mypoint.y+50)<=JumpAbility || fabs(Mypoint.y -50)<=JumpAbility)return 1;elsereturn 0;
}//上面已经分析过的DFS
int DepthFirstSearch(Point Mypoint,int number)
{
int i,answer = 0;Visit[number] = 1;if(IsSafe(Mypoint))return 1;else{
for(i=1;i<=CrocodileNumbers;i++){
if(!Visit[i] && Distance(Points[i],Mypoint,JumpAbility)){
answer = DepthFirstSearch(Points[i],i);if(answer)break;}}}return answer;
}int main()
{
int i,answer = 0;//先把"我"的位置赋值Points[0].x = 0;Points[0].y = 0;double FirstJump,IslandDiameter = 15;scanf("%d%*c%lf",&CrocodileNumbers,&JumpAbility);FirstJump = IslandDiameter/2 + JumpAbility;InitVisit();InsertCrocodiles();//这里就是我们上面提到的//第一次跳跃之后再用DFSfor(i=1;i<=CrocodileNumbers;i++){
if(!Visit[i] && Distance(Points[i],Points[0],FirstJump)){
if(DepthFirstSearch(Points[i],i)){
answer = 1;break;}}}if(answer)printf("Yes");elseprintf("No");return 0;
}
上面就是我的代码实现了
对于一些取巧的函数是参照了他人的优秀代码的
还是动脑筋想了2-3h
也是希望大家一起共勉
坚持下去吧
