【递归，搜索与回溯算法 综合练习】深入理解暴搜决策树：递归，搜索与回溯算法综合小专题（二）
优美的排列
题目解析
算法原理
解法 ：暴搜
决策树
红色剪枝：用于剪去该节点的值在对应分支中，已经被使用的情况，可以定义一个 check[ ]
紫色剪枝：perm[i] 不能够被 i 整除，i 不能够被 perm[i] 整除，此时分支就要执行紫色剪枝
设计函数
编写代码
N皇后
题目解析
本题的算法原理是比较简单的，难点在于剪枝操作和代码实现能力；
算法原理
解法：暴搜
决策树
决策树的任务：给一个行数，每次枚举这一行的一个格子，枚举的格子看是否同列或者主副对角线是否有皇后，没有则在该格子放一个皇后，并停止枚举这一行剩下的格子，递归下一行；
绿色剪枝：剪去遍历的格子所在列，出现其他皇后的情况；
紫色剪枝：剪去遍历的格子所在主副对角线，出现其他皇后的情况；
所以 N = 3，3皇后是没有合法的放置方法的 ；
当我们的行数为 N+1，说明已经枚举到了一种合法的结果；
如何剪枝：考虑当前位置，能否放上皇后
策略一：无脑循环
我们在遍历到一个格子的时候，使用四个循环判断当前格子所在行，列，左对角线，右对角线是否放有其他皇后，总体时间复杂度 O(N) = 4N * (2 ^N)；虽然时间复杂度高，但是也是可以通过的；
我们可以对这个方法进行优化，因为我们的决策树是每一行的其中一个格子用来放皇后，所以行是一定不会出现皇后攻击的情况的，所以只用看列，左对角线，右对角线是否放有其他皇后；
策略二：类似哈希表的策略
对于棋盘，我们分别定义两个 boolean 类型的数组 row[ ]，col[ ] ，用于判断某一行或者某一列是否放置皇后;
如果某个格子放置有皇后，对应的 row[ i ] ，col [ j ] 要置为 true ；后续再进行决策的时候，就可以先看看对应的 row，col 是否为 true，任意一个为 true 则不用再考虑本次枚举的格子；
接下来，我们来解决主对角线和副对角线的情况；
我们通过观察可以发现，当皇后要放置 N 个时，对应的主对角线和副对角线都是 2 * N - 1；
并且斜率分别是 1 和 -1，所以对于一条对角线，可以用y = x + b 或者 y = -x +b 来表示；
- 对于主对角线，则有 y - x = b ，纵坐标 + 横坐标为一个定值；
- 对于副对角线，则有 x + y = b ， 纵坐标 - 横坐标为一个定值；
所以我们再次定义两个 boolean 类型的数组 ，dig1，dig2 ，分别表示主对角线和副对角线；这两个数组的长度为 2*N ，用于存储所有的主对角线，或者副对角线；
用 b = y - x ，b = y + x 来表示某一条对角线的映射关系，当 dig1[ b ] == true || dig2 [ b ] == true，则说明该格子所在对角线放有其他皇后；
但是还有一个细节问题：
对于上图的主对角线，y - x 是一个负数，如果直接使用 dig1 [ b ] 会越界；
解决办法：添加上一个偏移量 n：y - x + n = b + n，让对角线统一向上移动 n 个单位，来处理截距为负数的情况；所以针对主对角线，我们判断的是 dig1[ b + n ] 是否是 true 即可；
编写代码
前期初始化操作
主逻辑
有效的数独
题目解析
本题并不是关于暴搜的题目，而是一个哈希表的题；我们通过讲解这道题的算法原理 ，为下一道题 解数独 做好铺垫
算法原理
解法：暴搜
我们先来定义一个 boolean 类型的数组 row [ ] [ ]：
第一个 [ i ] 表示的是数独表中的第 i 行， 第二个 [ j ] 表示的是在这一行有没有出现 j 这个数字；
如：row [ 2 ][ 4 ] 表示的是第二行有没有出现 4 这个数字，有的话 row [ 2 ][ 4 ] == true；
col[ i ][ j ] 数组同理，表示的是第 i 列是否出现了 j 这个数字 ;
除了用数组来表示数度表外，我们也可以用哈希表来表示数独表，并且用哈希表非常巧妙：
我们是以一个3 x 3 的小数独表作为一个单位格子的，此时下标就只有 0，1，2；
我们设置一个 boolean 类型的数组 grid :
grid [ 0 ][ 0 ] 表示左上角第一个 3x3 的大方格；
为了查看一个 3x3 的大方格所有数是否都出现过，我们再开一个空间给 grid：
如何定义小方格和大方格下标的映射关系呢？
当有一个元素的位置为 [ x , y ] ，映射的九宫格下标位置为 [ x/3 , y/3 ]；
编写代码
解数独
题目解析
算法原理
解法 : 暴搜
决策树
上图代表决策树的某一条分支，我们可以发现，当按照其中一条分支填到第一行最后一个格子时，第一行每使用过的最后一个元素可能是不能填入该格子中的；
那我们怎么知道这条分支的选择不能填满数独表呢？在遍历某个 ' . ' 的格子时，如果所有数都不符合题意，我们返回 false 即可；
这个代码的报错原因，就是没有对【因为前面的选择，导致某一个格子 1 到 9 都不能填入】的情况进行处理；
所以如果遇到【某一个格子 1 到 9 都不能填入】的情况，我们就应该向上返回 false，因此，我们的 dfs 应该设置 boolean 类型的返回值，告诉上一层，这种选法是否可以得到正确的数独，如果返回 false，我们就要让上一层的格子尝试下一个数；
dfs 的参数其实可以直接把 board 数组传入即可；在 dfs 中遍历 board ，专门处理 board[ i ][ j ] == '.' 的情况；
编写代码
初始化
填数逻辑
攻克难点
本题难点就是要想到 dfs 是 boolean 类型，并且要找到 dfs 中合适的位置进行返回；
对这三处 return 的解读
单词搜索
题目解析
算法原理
解法 ：深度优先遍历
模拟过程
我们以下面这个矩阵和 word 为例子来模拟过程：
刚开始，会先遍历矩阵中所有的元素，直到找到word 的第一个字符 ' A '
此时会对当前 A 的格子上下左右进行扫描，直到找到 B：
对于当前位置的 A ，上下左右位置并没有 B ，说明这个 A 不是我们要找的 A ，我们寻找下一个 A:
此时，我们发现当前 A 的位置右边和下方都有 B ，就需要递归这两种情况：
下方的 B 上下左右查找，并没有找到 C，我们遍历右边的 B
此时的情况和上面同理：
最终得到结果，返回 true：
如果按照上面的模拟过程，矩阵找不到 word ，则返回 false；
决策树
函数设计
细节问题一：如何避免走重复路径
问题描述
模拟过程
解决方法一： 设置一个 boolean 数组
定义一个跟原始矩阵相同规模的 boolean 数组 ：
用 visit 来标记当前位置，下次遍历到某一个位置时，通过 visit 查看这个位置是否已经被使用过；
解决方法二： 修改原始矩阵的值
当我们对某一个格子进行上下左右查找，查找到下一个字符时，把这个位置修改成 ' . '
面试的时候要问问面试官可不可以修改原始矩阵，修改原始矩阵的行为不保险；
细节问题二：用向量数组映射 ( i , j ) 位置的上下左右坐标
设置两个一维数组 dx[ 4 ] ， dy [ 4 ] ：
dx[ i ] 和 dy [ i ] 要能映射到同一个方向，映射关系如下：
我们使用一个 for 循环，就可以一个坐标的上下左右关系全部找到；如果要找 8 个方向，我们就定义两个长度为 8 的数组，来表示 8 个不同的方向；这种方法在二维数组表示方向的时候，是非常好用的；
编写代码
准备工作
在主函数中，先遍历一次矩阵，找到第一个 word[ 0 ] ，然后调用 dfs，从第一个 word[ 0 ] 所在位置开始找 word 剩下的元素；
主逻辑
代码细节详解
模拟上述对 return 会遇到的情况 ：
黄金矿工
题目解析
算法原理
本题的算法原理和上一题是一类题型，解法大差不差，只是一些细节问题不同；这一题先尝试自己编写代码，再根据老师的视频改进；
解法：暴搜
编写代码
编写历程
那么，我们什么时候在主函数更新结果呢？如果要设置递归出口，就要再写一层 for 循环，判断上下左右的 vis ==true || grid == 0，对于这道题是没有必要设置递归出口的；
只需要找到一轮递归的最大值 tmp 即可，并且更新 ret 即可；所以我们一进入 dfs 就更新 ret；
总结
关于更新结果的问题是难点：尤其是在哪里更新结果？这么更新结果有什么用？为什么要这样更新结果？
每次作出一题，都要想清楚这几个问题，并且学会新的处理细节问题的方式，如：
- 二维矩阵搜索路径时，避免走重复路径的方法；
- 使用向量坐标表示一个格子不同的方向；
不同路径Ⅲ
题目解析
算法原理
解法 ：暴搜
编写代码
优化
减少循环次数：
继续优化
我们可以对递归出口进行优化，原来是只有合法路径才 return ，现在是只要走到终点就 return：
总结
关于暴搜的题目，算法原理其实并不难，重点考察的就是我们的代码能力，以及能否发现细节问题，并且对细节问题进行合理的处理；