5-13 地下迷宫探索 (30分)——DFS

男娘i 2022-09-27 06:23 167阅读 0赞

sthink:  
1开学后一直没有写博客，感觉明显没有假期时候的学习效率，不管是专业课还是别的课程，感觉自己很难达到第一学期的激情与效率，相对于别的同学感觉自己变得迷茫了，不再像是第一学期一样谦逊，老师说过看不清前方的时候就坚持那些让自己能力不断提高的事情，或许会很累，但那总不至于在以后看清的时候却发现自己晚了，似乎每个人都是在摸索中前进，而不是非等到一切明朗时候才去做，自己还年轻，自己应该拼搏，而不是纠结在一些繁琐的感情上面，既然自己并不能打动别人，那就不要傻傻的幻想，要通过正在建立的努力展现理性的价值观世界观人生观建立自己的理想和梦想，不优秀的自己没必要矫情，那样只会显示自己的软弱，至少对于现在自己所认识的一切想法的实践离不开物质基础，昨天晚上以及近几天的天梯赛训练自己表现的很菜，菜得很，如果照这个情况发展，自己必定没有资格与优秀的同学去参加天梯赛，当自己迷茫徘徊在为什么知识点都忘记的时候，优秀的同学都已经开始勇敢的补题，自尊的耻辱可以使人奋发前进，而不是放弃，之前的自己进入504可以说运气占了很大比重，时间紧凑，那就缩减不必要的时间浪费，提高自己的 效率，不管是学习还是生活，少说话，多思考，多做事，自己有点害怕写博客可能还有一个原因，之前自己可以在博客上自由自在的写出自己的心理感受而不必担心会有人知道自己，或许是因为知道了有的同学发现了自己，感觉自己的内心的小世界不在那么单纯的做题补题反思，但那何尝不是因为自己当初无法做到谦虚学习，进而埋下了浮躁的根，再就可能是因为或许有了一个学霸徒弟，虽然自己一直不同意她叫自己师傅，但真的很感谢她，若不是她当初对自己的开解，或许自己也只是一名不敢多想的小学渣，现在是一名敢想的小学渣，谢谢  
2回归题目，题目作者提示用DFS，但自己竟然当时忘了DFS是什么，还把最短路径给搞混了，但是竟然在尝试用最短路径来解题，真心感觉自己应该反思一下知识体系的建立，深度优先搜索通过递归思想来实现，不断地深入，知道找到题目最优解，而广度优先搜索类似于树中的层序遍历，通过队列思想来实现

5-13 地下迷宫探索 (30分)

地道战是在抗日战争时期，在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事，如下图所示。  
我们在回顾前辈们艰苦卓绝的战争生活的同时，真心钦佩他们的聪明才智。在现在和平发展的年代，对多数人来说，探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。  
假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式:  
输入第一行给出三个正整数，分别表示地下迷宫的节点数NNN（1

#include <stdio.h>
    #include <string.h>
    
    int e[1004][1004], vis[1004], book[2008];
    int n, top;
    
    void DFS(int v);
    
    int main()
    {
        int m, v;
        while(scanf("%d %d %d", &n, &m, &v) != EOF)
        {
            int a, b;
            top = 0;
            memset(e, 0, sizeof(e));
            memset(vis, 0, sizeof(vis));
            for(int i = 0; i < m; i++)
            {
                scanf("%d %d", &a, &b);
                e[a][b] = e[b][a] = 1;
            }
    
            vis[v] = 1;
            DFS(v);
    
            if(top != 2*n - 1)
                book[top++] = 0;
    
            for(int i = 0; i < top; i++)
            {
                printf("%d%c", book[i], i == top - 1? '\n': ' ');
            }
        }
        return 0;
    }
    
    void DFS(int v)
    {
        book[top++] = v;
        for(int i = 1; i <= n; i++)
        {
            if(e[v][i] == 1 && vis[i] == 0)
            {
                vis[i] = 1;
                DFS(i);
                book[top++] = v;
            }
        }
    }