题目描述
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下 5 张来，要求必须是连着的。
（仅仅连接一个角不算相连） 比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
DFS思路：
我是参考b站的Eric_Richard博主给的思路。由于要是想以某个格子作为起点，然后再依次去选取五个连接的格子的话，这种思路会需要把这多种情况记录起来再去去重，然后最后得出结果。所以我这道题选取了这个博主的思路，就是把全排列选取随机的五个点，然后再去判断这五个点是否是连通的。全排列可以用全排列函数（next_permutation()或prev_permutation()，具体用法也可以看我的另外一个blog：蓝桥杯——2013B组真题第九题 带分数）
在《算法笔记》中可以了解到，“使用递归可以很好地实现DFS。这个说法并不是说深度优先搜索就是递归，只能说递归是深度优先搜索的一种实现方式，因为使用非递归也是可以实现DFS的思想的，但是一般情况下会比递归麻烦。不过，使用递归时，系统会调用一个叫系统栈的东西来存放递归中每一层的状态，因此使用递归来实现DFS的本质其实还是栈”。
代码如下：
BFS思路：
跟DFS一样的思路，还是利用全排列随机选取5个点，然后通过BFS来判断每次所要剪的五个格子是否是连通的（即连着的）。跟DFS相比，多了一个判断元素是否已经入队的二维数组。
参照《算法笔记》，广度优先搜索（BFS）一般由队列实现，且总是按层次的顺序进行遍历，其基本写法如下（可作模板用）：
代码如下：
结果：
116
总结：
DFS是通过从一个点一直往下走，直到遇到"死胡同"（即退出条件），才一点一点往后走，并加入下一个分岔口。BFS是通过一层一层的，从一个点的每一层出发，直到找到出口。（这里属于个人见解，要是觉得不对的，还请斧正！）
在BFS中设置的inq数组的含义是判断结点是否已入过队，而不是结点是否已被访问过。区别在于：如果设置成是否已被访问，有可能在某个结点正在队列中（但还未访问）时由于其他结点可以到达它而将这个结点再次入队，导致很多结点反复入队，计算量大大增加。因此BFS中让每个结点只入队一次，故需要设置inq数组的含义为结点是否已入过队而非结点是否已被访问。
最后指出，当使用STL的queue时，元素入队的push操作只是制造了该元素的一个副本入队，因此在入队后对原元素的修改不会影响队列中的副本，而对队列中副本的修改也不会改变原元素，需要注意由此可能引入的bug（一般由结构体产生）。
网友评论
最新评论