DS第六章学习小结

以你之姓@ 2021-12-17 10:23 315阅读 0赞

**一、知识总结**

先上思维导图

![1627752-20190519202112384-737552169.png][]

本章“图”可以说是树的延伸，所以说理解起来容易一点，不过小问题还是挺多的。图的存储结构是通过使用邻接矩阵和邻接表实现的，并且在输入的时候还会的到边数和顶点数。我认为本章的重点应该在**图的创建，最小生成树以及最短路径问题这几点上。**

**二、作业实践**

判断要点：

①湖是一个正方形，边长为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][https_www.jianshu.com_p_bce71b2bdbc8]

推荐中国大学mooc北大郭炜老师的课（[https://www.icourse163.org/learn/PKU-1002029030?tid=1002785058\#/learn/content][https_www.icourse163.org_learn_PKU-1002029030_tid_1002785058_learn_content]）

# 四、目标 #

上次的目标基本达成，但是写代码的时间还是有点少。

下一个目标就是提高自己的底层算法，不要到写题的时候疯狂翻书，真正的脚踏实地去编一个程序；还有复习一下之前的内容，稳定基础。把自己的思维方法迁移到各个知识点上。

转载于:https://www.cnblogs.com/hxyawsl/p/10890643.html

[1627752-20190519202112384-737552169.png]: /images/20211217/4caf0c2c9df94708b924c0e5e2b6be78.png
[https_www.jianshu.com_p_bce71b2bdbc8]: https://www.jianshu.com/p/bce71b2bdbc8
[https_www.icourse163.org_learn_PKU-1002029030_tid_1002785058_learn_content]: https://www.icourse163.org/learn/PKU-1002029030?tid=1002785058#/learn/content