一、知识总结
先上思维导图
本章“图”可以说是树的延伸，所以说理解起来容易一点，不过小问题还是挺多的。图的存储结构是通过使用邻接矩阵和邻接表实现的，并且在输入的时候还会的到边数和顶点数。我认为本章的重点应该在图的创建，最小生成树以及最短路径问题这几点上。
二、作业实践
判断要点：
①湖是一个正方形，边长为100，中心在(0,0)四个定点分别为(50,50),(50,-50),(-50,-50),(-50,50)，湖中小岛直径是15，半径7.5.如果007步长d大于50-7.5=42.5，就可以直接从小岛直接跳到湖岸
②判断007能否从岛上跳到湖中某一点A(x, y)，即d+7.5>=sqrt(x*x+y*y);也就是(d+7.5)*(d+7.5)>=x*x+y*y;（FirstJump函数）
③判断007能否从A点直接跳到湖岸，当007步长大于A点到湖岸的距离时，说明可以到达换，即d>= 50-| x | 或者d>= 50-| y |;（IsSafe函数）
④如果跳上一点不能直接跳到湖岸，那就跳上另一点看能不能跳到湖岸满足③条件，这里就是判断能否从A(x1,y1)点跳到B(x2,y2)点，如果007的步长d>=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)),即d*d >= (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)。如果满足，说明可以从A点跳到B点，否则不行。（Jump+DFS函数）如果不行，就继续递归尝试另一个B点，如果此路不通，返回②条件，换一条路，换一个起点A继续尝试，如果所有路都无法到达对岸，说明无法逃生。
代码如下
#include<iostream> using namespace std; #define MAX 100 #define YES 1 #define NO 0 int d;//步长 int Visited[MAX];//标记矩阵 /*初始化标记矩阵*/ void ResetVisit(){ for(int i=0;i<MAX;i++) Visited[i]=0; } int N; //存储鳄鱼方位 struct Point{ int x; int y; }Point[MAX]; /*第一跳*/ int FirstJump(int i){ int x=Point[i].x; int y=Point[i].y; if((d+7.5)*(d+7.5)>=(x*x+y*y)) return YES; else return NO; } /*是否能从i点跳跃至j点*/ int Jump(int i,int j){ int x1=Point[i].x; int y1=Point[i].y; int x2=Point[j].x; int y2=Point[j].y; if(d*d>=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) return YES; else return NO; } /*在i点判断是否能到达岸边*/ int IsSafe(int i){ int x=Point[i].x; int y=Point[i].y; if(x<0) x=-x; if(y<0) y=-y; if(d>=50-x||d>=50-y) return YES; else return NO; } /*dfs*/ int DFS(int i){ int answer; Visited[i]=true; if(IsSafe(i)) answer=YES; else{ //循环遍历每个节点 for(int j=0;j<N;j++){ //如果该节点未被访问，且能从j结点跳至j结点 if(!Visited[j]&&Jump(i,j)){ answer=DFS(j); if(answer==YES) break; } } } return answer; } /*解救007*/ void Save007(){ int answer; ResetVisit();//初始化标记矩阵 for(int i=0;i<N;i++){ if(!Visited[i]&&FirstJump(i)) answer=DFS(i); if(answer==YES) break; } if(answer==YES) cout<<"Yes"; else cout<<"No"; } int main(){ cin>>N; cin>>d; for(int i=0;i<N;i++){ cin>>Point[i].x; cin>>Point[i].y; } Save007(); return 0; }
三、参考及分享
https://www.jianshu.com/p/bce71b2bdbc8
推荐中国大学mooc北大郭炜老师的课（https://www.icourse163.org/learn/PKU-1002029030?tid=1002785058#/learn/content）
四、目标
上次的目标基本达成，但是写代码的时间还是有点少。
下一个目标就是提高自己的底层算法，不要到写题的时候疯狂翻书，真正的脚踏实地去编一个程序；还有复习一下之前的内容，稳定基础。把自己的思维方法迁移到各个知识点上。