食用说明:这只是一个笔记,不是教学(可以用于考前复习)
(其实更推荐去看我老史的问题模型总结)
(这里给出的例题不是我自己出的嗷)
一.从抽奖开始的旅程
抽奖1:3次抽取,记录编号后放回
所以:
就可以了.
抽奖2:n次抽取,记录编号后并放回.
此时发现,不能再用简单的循环了;于是开始使用一些函数:
抽奖3:n次抽取,记录编号无放回
与抽奖2唯一的区别在于:第一轮抽出的球,第二轮无法再抽出
我们无法直接将这个选项删除,但是可以增加一个bool数组对已经抽出过的球进行记录
也就是说,我们的for循环内需要开始增加条件:
解释一下回溯的意义:
先看这张图:
for循环第一轮从1号球开始,然后判断其没有被抽过,标记它,然后进入第二轮抽球(第一轮抽了1号球),然后从2,3里选;假设第二轮抽球选了2号球,然后判断其没有抽过,标记它,然后进入第三轮,然后抽第3个球,标记它.
至此,一轮结束.
值得注意的是,此时的1-3号球全部标记,如果没有回溯(也就是消除标记),那么下一次抽取,将没有球可抽(能抽取一个球的前提条件是它没有被抽过)
所以,需要进行回溯.
如果觉得对回溯的概念和用法不不太明白,可以去看主播新写的一篇考试总结,里面更加详细地讲述了回溯.
抽奖4:n个球,m次抽取,记录编号后并放回,求出编号之和为p的方案总数
记录编号后并放回:不需要vis数组
编号之和为p的方案总数:其实没有过多的改变,只需要在if语句里加一个特判,比如这样:
抽奖5:n个球,m次抽取,记录编号后并放回,求m次抽取的编号恰好是从小到大排好序的方案数.
与抽奖4一样,"从小到大排好序"这个要求,只需要在if语句里加判断就好,像这样:
二.卷入迷宫的纷争
迷宫的相邻点:这题其实没有用到DFS,只是熟悉坐标数组和学习如何判断坐标是否合法.
这是一般人类概念中的坐标:
哇,坐标拿了MVP!
那么,在得知(x,y)的情况下,如何去计算出(x,y-1) (x-1,y) (x+1,y) (x,y+1) 呢?
这里我们最好不要一个个去枚举,这样显得有点笨笨的,这里可以用简单且高效的方法,坐标数组(应该是这么叫的):
然后用一个for循环开始枚举坐标:
但是,同学们可能会发现,当x=1,y=1(此时的下标从1开始,(1,1)也就是左上角)时:
x-1或y-1(也就是坐标为(0,1)或(1,0)时)产生的坐标是不合法的.
所以,我们需要在每一个坐标计算完后都用一个if语句去判断这个下标是否合法,比如:
(这个判断的写法有很多种,这里写出的只是其中一种哦)
迷宫之判定:(题意自行阅读)
DFS模板题目之一,先说一下思路:
其实就是一个个的坐标去轮,去过,类似于抽奖,但是"球"变了:
一个球抽完后,可以再去抽下一个球.
这里的走迷宫,是抽完后无放会的类型,因为可以看到,每次走到下一个坐标后,都有可能回到原来的位置
所以,我们需要一个二维的vis数组,来记录我们曾到过哪些坐标:
这是,还需要考虑的是,如何去实现呢?
可以考虑的是,将坐标的位置直接放在函数里:
如果走通,就直接输出"YES"就可以了,像这样:
这里需要注意的一个点是:很多小伙伴都会忘记将初始位置的vis标记(这是非常知名的!一定要注意!)所以一定要先写好:
迷宫之最少花费时间:相比上一道题,多出了"怪兽"和"最少花费"
先说最少花费:首先既然涉及到了时间,那么就需要在我们的函数里加变量了:
这个时候可能会有人问:为什么不直接设一个在外面的变量t来记录时间呢?
可以这张图:
假设星期一小明从A出发前往B,他消耗了14的能量;星期二小明又从A出发前往C,他消耗了20的能量.
那请问小明在星期二消耗了多少能量?
答:20.
注意,是20,不是34;小明在星期二消耗的能量和他在星期一消耗的能量没有任何关系;那么走迷宫
同理:
如果将t设在dfs函数中,那么,它的每一次变化都是单独的;但如果将t设为全局变量,且处理不当的话,那么它行走路线1的时间可能会加在路线2上.
(如果还是不清楚,也可以去自己尝试哦)
然后是"怪兽":这个问题其实很好解决,只要把每个怪兽对应的消灭时间加上就好了(注意,除此之外还要再加一分钟,因为小明走到空地上就需要花费一分钟)
走迷宫:没有太大的变化:比上一题少了"怪兽"和"时间"的存在,但是多了"要求所有走的路中没有重复的点",还要输出所有可行路径.
先说"要求所走的路中没有重复的点":这个要求不需要担心,因为前期提到过的vis数组的存在,我们已经把到过的点都标记了,所以一条路径中是不会有重复的点的.
然后再说如何输出所有可行路径:考虑到有一些路径可以开始,但可能走不到终点,所以我们不能走一步输出一步.但是我们可以用一个结构体数组或者两个int数组来存储每次的(x,y)坐标:
(这里提一下,每次记录玩坐标后,不需要再去清楚,因为可以覆盖)
而每次存储的下标也可以向上一题里一样,在函数内设置变量来存储,比如:
DFS函数里的一些细节前文好像没有提到,所以也把一些框架提一下:
需要注意的是,没有路径时应该输出-1
三.棋局中的诡谲云涌
(因为准备考试和预习,这边断更了几天;重新开始更,如果题目难度和讲解详细度有波动的话请见谅,也可以直接提出哦,一定会改哒!)
黑白棋盘:相当基础的问题,运用了坐标数组.
大致题意:问从一个坐标,上下左右地在一定范围内走,能走多少格子(只是略微施加了"黑色"的要求,然后要自己去找起点)
唯一要注意的点是,这题是多测,也就是意味着它可能有很多个测试点,直到输入0 0 为止.
教一下怎么写多测吧:
就是一直循环,直到它输入0 0 直接结束就好了
(这题不难,所以主播不细讲,会更加详细地讲一下下一题地八皇后问题)
八皇后:经典题目!
题意:想要在一个8*8的棋盘中放置8个皇后,要保证每个皇后在不同行,不同列,不同对角线(温馨提示:对角线有两条).
现在要求可怜的学牲(也就是你)输出所有可能的摆放情况:每行中,皇后摆在哪一列.
就像这样:
先说思路:其实和迷宫差不多啦,也是一个一个坐标的遍历+回溯.
难点在于:如何去判断一个坐标能否放置皇后呢?
理清思路:一个坐标如果能放置皇后,需要与其同行,同列,同对角线都没有其他皇后.
首先想到用bool数组去记录行,列,对角线的放置情况:
这时可能有小伙伴问:为什么没有行?怎么用数组去记录对角线位置?
首先回答第一个问题:
不设置行的标记数组是因为本身在程序运行的过程中,我们是有办法保证不让行重复的.
这就不得不提如何编写我们的程序了:
首先,在此次DFS中,会遍历八次,每一次遍历就是在找每一行中,皇后摆放在哪一列:
比如在第6次遍历中,就是在找第6行,皇后应该放在哪一个位置.
在这样的程序里,行是不会重复的,所以不需要额外去做一个行的bool数组来记录.
然后是第二个问题:怎么用一维数组去记录对角线位置?
先看此图:
假设蓝色的方块是我们现在所处的位置:(x,y) -> x行,y列.
绿色的方块是对角线1,黄色的是对角线2.
仔细观察对角线1和对角线2的x,y
你有发现什么规律吗?
没有的小朋友:
(鹅鹅鹅鹅,哈哈哈哈哈哈.这个是我的老史在第二次考试中写的评语,它的完整版在本篇末尾)
好了,严肃一点,我们继续说说对角线1和对角线2中x,y的规律吧:
对角线1:可以发现所有绿色方块中,x-y+8是一样的(这个规律在这张图中体现的不是很明显,大家可以自己去写几个其他的,也是这个规律)
说一下这个x-y+8是怎么得出的:
因为如果x-y是负数的话,是不行的;abs(x-y)也是不行的(这个后面会提到,如果现在搞不懂可以直接跳过,后面提到时在回来看)
对角线2:这个的规律比对角线1简单很多,也很容易发现:所有黄色方块中,x+y是相等的.
好了,有了这两个规律,我们就可以做一下代码实现了:
比如说,我们现在决定把皇后摆放在x行y列,那我们就可以这样记录:
现在主播解释一下上文中留下的疑问:为什么要用x-y+8:
首先,x-y可能会是负数,但是在标记时,数组下标是不能有负数的.
所以我们现在有两个选择:
1.x-y+8
2.abs(x-y)
来说一下为什么第二种不行:
举个栗子:(3,1) (1,3)这两个坐标
)
3-1=2
abs(1-3)=2
如果使用abs,这两个坐标的标记点是相同的,但是他们并不在同一条对角线上(对角线1,不是对角线2)
所以不能使用.
反观x-y+8:
3-1+8=10
1-3+8=6
是不会有混淆的(至于为什么要用8,因为x-y最小也只会达到-7,主播也比较习惯下标从1开始,所以就使用8)
四.田野中的靓丽风光
To be continued . . .
