用一个寒假学算法_第二周(上) 栈/深度优先搜索
第二周的算法讲解
由于本人最近比较懒，所以第二周的等到星期二才动手写，本周我们将学习一个数据结构知识“栈”，两个常用的算法，由于比较常用，所以会多放题目让大家多写写。本周也一起加油吧(ง •_•)ง
·开始本周的算法学习！·
#1
“栈”
栈算是一种非常有趣的数据结构，如果用一个词概括它，那就是先入后出，不过，这样好像不是很形象，这里我用图画让大家对于栈的运作模式有个更加直观的了解
上面这张图把栈，包括入栈push，出栈pop的过程都模拟了一遍，相信你现在应该有大概的印象。
而c++里也有对应的stl容器，也就是stack，头文件是: stack.h [具体用法大家可以自行百度]
而平时我们也可以用数组模拟stack。
下面是用数组模拟stack的过程
设置对应的尾指针，存放最近插入的数的下标，记为idx，初始值为0；
每当push一个进来x时，stack[idx++] = x;
要查看第一个数时，stack[idx-1]
要pop[即将最后一个数出栈], idx--;
下面用一道题让大家熟悉栈的使用
题目链接：
https://www.luogu.com.cn/problem/P1165
我们可以看出来，题目的目的是：
让我们边模拟栈操作，同时告诉他们栈里的最大数是多少。
这里推荐大家先做完这道题再来看我的写法，注意可以利用栈的特点。
题目分析
首先我们先分析题目的要求，选择0时，将一个数入栈；选择1时，则将最后加入的去掉，那就是出栈；选择2时，输出此时库里的最重的东西是什么。
其中比较麻烦的问题是如何随时输出库里的最大的重量。
看到这个你可能会想，我拿一个变量存放最大值不就行了么，但是当我取出时，这个最大值可能就会发生变化，难道我要每取出一次就遍历一遍么，这明显太浪费时间了。
那我们该怎么办呢？其实我们可以这样想，当每放进去一个东西时，我记住每个时刻最重的东西不就行了么？
那么我取出多少件东西的时候，我就把每一时刻最重的东西更新为前一时刻最重的东西不就行了么？
确实，我们可以这样做，但是这其实也是另一种形式的栈！
当我们每次放入东西时，我们可以拿另一个栈存放放入东西那一时刻我们最大的重量，当取出物品的同时，我们也把存放每一时刻最大重量的栈出栈，这样我们栈顶就永远显示我们放入每个物品时所对应的最大重量。
下面是自己写的代码：
这里其实用一个maxn栈也行，但是为了方便大家，所以使用两个栈，表现出来更加直观。
Learning
#2
“深度优先搜索(DFS)”
DFS，即深度优先搜索，也被称为暴搜，是一种利用递归特点的搜索方法。
和我们走迷宫有点相似，当我们不知道能不能另一端时，我们可能就会把所有路都走一遍，说不定会走到迷宫的终点呢？
那DFS是如何实现的呢？
这里用走迷宫的道理来教你。
走迷宫的时候，每走一步，就要抉择该走哪个方向，那就走一步我就标记(防止自己重新走一遍浪费时间)，标记了的就是我走过了的；当我发现走到绝境了，那就原路返回到前一个交叉口(递归回去)。返回了就往其他没走过的方向走，又走到绝境就又返回，直到无路可走为止。
看完之后是不是觉得就是一个递归的过程。
那就先拿一道题来练练手吧
题目链接：
http://poj.org/problem?id=1426
可能有的小伙伴会觉得，我天，这就放一道英文题目，好可怕。我表示别慌，静下来，有翻译软件。
这里给下题意：给一个两百以内的整数，要求找到由0和1组成的可以被其整除的整数
这题其实就是一道典型的dfs题目
这次我先放我的做法
大家看到之后可能会想，这不就是递归么？
是的，我也认为这就是递归而言，但是dfs其实还有各种剪枝之类，但无疑它就是一种暴力搜索。
别跑题，我们来分析下为啥要这样写哦。
首先，d是用来防止数字超过long long的，如果超过了就返回去找其他方法。其次flag是找到的标记，毕竟找到就没必要找了，所以return。
然后每一位都有两种可能，所以我们要列出来进行判断，才有最后面两个自我调用。
然后放我自己写的解法(其实是n久之前的了)：
Learning
#1
“DFS(2)”
第二部分其实也是做题。
题目链接：
https://vjudge.csgrandeur.cn/problem/LightOJ-1012
题意：
给你一个由起始点'@', 空地'.', 水'#'，问你王子可以居住的是哪几个块，注意水'#'是不能居住的，空地才可以，起始点也包括。
之前有讲过，我们需要把每个走过的地方标记一下，这里有个取巧的方法，就是把走过的地方都当成不能走的地方即可。然后每走一个我们都要num++，而且还要往四个方向看看能不能走，也就是+b[k][0], +b[k][1]这一部分，这里其实是把四个方向存在一个数组里面了，具体看完整代码。
然后注意搜索过程中的边界问题要记得判断，然后遇到空地才能调用下一步，不断继续find，直到找到的时候return，不过此处让它简单的终结即可，要不要遇到终点才返回都可以。
本人写法：
最后放两道题让大家自行学习下
https://vjudge.csgrandeur.cn/problem/LightOJ-1049
https://vjudge.csgrandeur.cn/problem/LightOJ-1111
Learning