南哪2022-6-recursion EX 搜索

### 特别注意：P2383是最难的题，需要考虑大量的剪枝优化，建议放到最后做 #### 搜索的题目一开始做会有一点点难理解，练多了才会好，所以这次题目难度变化不会很大，但是数量增加（不过貌似也不是特别多的亚子） #### P1433不要听题解瞎说，正常做数据范围应该是能过的 #### 这里到处都是重点，请各位同学一定要看到最后。 各位好啊！又是我，某CQ！ 发现大家递归好像做的还行了，但是好像基于递归来暴力求解一些问题还不太熟练。 这次我们将从全排列问题开始讲起，将基于递归的搜索的通用做法来给大家过一遍。 将1到n这n的数字按某种顺序排好，一共有多少种排法？并且我们要求你把所有的排法情况按照字典序输出。 ```c int a[N]; bool vis[N]; void qpl(int now) { if (now > n)//所有的位置都放好数字了，直接输出 { output();//这个输出自己写 return; } for (int i = 1; i <= n; ++i) if (!vis[i])//如果这个数字没有被用过 { vis[i] = true;//标记为用过 qpl(now + 1);//搜索下一位 vis[i] = false;//这个数字不用了，取消标记 } } ``` 实际上，上面的程序里面已经标注的很清楚了。 在每个递归的子问题当中，我们只要处理当前这一位我们要填什么，这一位具体能填哪些数字由前面已经填过的位置决定。 当填好这一位，我们去填下一位。 当所有的位置都填好了，我们就直接输出，然后返回去找别的填数的可能。 当返回前一位的时候，这一位上原本填的数字不要了，所以一定要记得把标记去除。 在这里我们注意到几个问题，它们也正是搜索要注意的内容： 首先，因为这样的穷举方式是基于递归的，所以终止条件依然少不了，不然就等着死循环吧。 其次，能用这种穷举来解决的问题，某个子问题的求解不会被之后求解的另一个子问题所影响，而是只会被在其前面的子问题影响（或者子问题之间根本没有关系）。 然后就是每一个子问题的具体求解，在求解下一个子问题之前一定要把当前子问题对之后子问题求解造成的影响记下来，当返回的时候，一定要把标记取消，否则会有意想不到的（或者意想得到的）问题。 另外需要提醒的一点就是，递归中的错误很可能让人摸不着头脑，最适合的解决方法除了调试，也就只有把整段代码的逻辑重新过一遍才有可能解决了。 听说有些老师在课上已经讲过了八皇后问题。 实际上，在全排列这一代码的基础上稍加修改，我们就能得出求解八皇后问题的方法。 我们按照8 x 8棋盘的行来分，显然每一行只可能有一个皇后，每个皇后的列号肯定也不一样，那么我们只要枚举每一行的皇后的列坐标就行。 所以八皇后问题就是一个n = 8的全排列问题，不过，条件的判断略有不同。 通过全排列我们已经解决了皇后们出现在同一行/列的问题，现在我们需要解决斜角上冲突的问题。 如果说我们把前面已经找过的皇后全部过一遍一个一个判断，固然是可以的，但是这样做，如果我们将问题扩展到n皇后问题，就显得不那么优秀了，容易超时，那怎么办呢。 注意看某一条从右上到左下的斜线上每一个点的坐标，你会发现，同一条斜线上的点，它们的行号和列号相加是相等的。 从左上到右下的斜线同理，自己算一下这些点的行号和列号之间大概有什么关系。 八皇后问题在洛谷上能找到这道题，在这里就不重复放这道题的具体解法了，这道题会被选在题单里面，如果仍然不是很理解，可以去看看题解。 接下来进入十分重要的一环，在二维图上的路径搜索： 拿一道简单的题目来举例： 一个n x m的地图，从（1，1）走到（n，m），只能朝上下左右四个方向走，图中有一些障碍物，求最少要走多少步才能到终点。 注意这里障碍物不止一个，可能有很多个，采取之前蚂蚁寻路的那种通过讨论绕开障碍物的做法是不可取的。 我们先用递归的思路来考虑这个问题： 终止条件： 当我们到达终点或者没有路走了，我们就不需要进一步考虑下一个子问题了。 之后的问题是否对前面的问题有影响： 你走到某一个点，并不会影响前面你走过某个点。所有后面的问题对前面是没有影响的。 具体子问题做法： 当你在点（x，y）时，除了来路，你有三个方向可以走： 如果某个方向上是障碍物或者地图边界，不能走，直接跳过这一个方向。 如果某个方向上是能走的路，而且**当前路径**之前**并没有走过**，那么就走过去。 所有的情况都探索完了，退到上一步，继续去找其它的情况，此时记得要把当前的标记去除（因为你需要标记某一个点你有没有走过）。 这里有一个小技巧就是如果是障碍物，你可以直接把它标记为已经走过，这样就不会走上去了。 来看一下展示具体做法的代码： ```c const int dx[5] = {0, 1, -1, 0, 0}; const int dy[5] = {0, 0, 0, 1, -1}; //定义方向，减少搜索过程中复制粘贴的工程量（以及其中高得离谱的错误率），这里为了方便，用0占掉了第一格 int ans = 2147483647, n, m;//我们要找到最短路径，那么答案初始值应该是最大的，这样才能保证答案最短 bool vis[N][N];//存图实际上有vis数组就够了 void dfs(int step, int x, int y)//dfs指的是深度优先搜索(Depth first search)从整个搜索过程思考一下为什么它叫这个名字 { if (vis[x][y])//如果这个位置并不能走，直接返回 return; vis[x][y] = true;//走过了，打上标记 if (x < 1 || x > n || y < 1 || y > m)//如果这个位置在地图范围之外，也不能走，直接返回 return; if (x == n && y == m) { if (step < ans) { ans = step;//更新答案，同时不要忘了返回，不要继续往下找了 return; } } for (int i = 1; i <= 4; ++i)//枚举方向 { int nx = x + dx[i], ny = y + dy[i]; dfs(step + 1, nx, ny);//无所谓，边界条件会出手，直接走 } vis[x][y] = false;//走过了，取消标记 } ``` 这便是最基本也是最常见的两种搜索，其它的搜索也许在形式上略有不同，但是也逃不过这种思路，记好某CQ总结的几点注意，绝对能把搜索写对。 下面讲一点搜索的优化小技巧： 如果你将整个搜索过程画图表示出来，它很像一个从根开始不断分叉的树，我们想要优化搜索，就需要将其中我们不需要的一些分支尽可能的去掉，所以我们很形象地把这种搜索优化方法称作剪枝，实际上就是通过添加一些边界条件来跳过一些不必要的搜索。 其实上面那道图上寻路就可以进行剪枝优化，我们稍微修改一下上面的代码，就能得到： ```c const int dx[5] = {0, 1, -1, 0, 0}; const int dy[5] = {0, 0, 0, 1, -1}; //定义方向，减少搜索过程中复制粘贴的工程量（以及其中高得离谱的错误率），这里为了方便，用0占掉了第一格 int ans = 2147483647, n, m; bool vis[N][N]; void dfs(int step, int x, int y) { if (vis[x][y]) return; vis[x][y] = true; if (x < 1 || x > n || y < 1 || y > m) return; if (step > ans)//如果已经走的步数都超过了现有的答案，那他之后怎么走都不会比答案更好了，走它干嘛 return; if (ans == n + m - 2)//答案已经最小，就没必要求下去了 return; if (x == n && y == m) { if (step < ans) { ans = step; return; } } for (int i = 1; i <= 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; dfs(step + 1, nx, ny); if (ans == n + m - 2)//原理同上 return; } vis[x][y] = false; } ``` 通过添加一些边界条件，我们去掉了一些没必要的搜索，优化了搜索的效率，这在一些题目里面，可能会成为至关重要的一环，说不定加了剪枝，你的程序虽然还是暴力，依旧很烂，但是就是能过，因为你实际上比一般的搜索优化了不少。 接下来，题单中有一些搜索的题目，解决它们的任务就交给同学们辣！ ##### 注：dfs也可以用来填充图上的连通块（这其实十分重要！）