【搜索】暴力专项训练

### [船新版本：系统复习搜索算法](https://www.luogu.com.cn/blog/LinearExpectation/search-algorithm) ------- ## 引言 - 搜索是算法的基础，往往编写难度低且容易查错。 - 暴力搜索可以帮助我们拿到一些正解难度较高题目的部分分。 - 暴力普适性强用处广，通过暴力获得骗分亦是考场上不错的选择。 OI 界有句话叫做“暴力打满”，即一次比赛拿到所有的暴力的分，考虑到在 NOIp/CSP 中暴力分较多，况且常数优化和暴力的一些剪枝也可以拿到更多分（而且像普及组 T1/T2 以及提高组的 Day1 T1 撰写正解难度并不高），拿到省一其实希望很大。 但是暴力也要找准方向，纯粹的枚举是愚蠢的，那么，让我们开始吧。 ## $\rm\small DFS$ 深度优先搜索 深度优先搜索（缩写 DFS）是对一个连通图进行遍历的算法。 其思想是从一个顶点 $V_0$ 开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，反复进行上述过程，从另一条路开始走到底，这样就可以较为有序地遍历所有的节点，这种尽量往深处走的概念即是深度优先的概念。 这样可以按顺序遍历所有的点，时间复杂度较高，所以称为暴力搜索，我们通常采用递归的形式编写程序，这样的搜索可以通过剪枝优化，从而使重复的搜索减少。 【例题】[P1596 \[USACO10OCT\]Lake Counting S](https://www.luogu.com.cn/problem/P1596) ```cpp void dfs(int x,int y){ a[x][y]='.'; int dx,dy; for(int i=-1;i<=1;i++)for(int j=-1;j<=1;j++){ dx=x+i; dy=y+j; if(dx>=0&&dx<=n&&dy>=0&&dy<m&&a[dx][dy]=='W')dfs(dx,dy); }return; } ``` 有一些基础的题目在洛谷没有，所以我创建并改良了几道类模板题供大家练手，详见[此处](https://www.luogu.com.cn/paste/ath8dye4)。 ## $\small\rm BFS$ 广度优先搜索 我们首先访问顶点 $v_i$，然后访问 $v_i$ 的所有未被访问的邻接点 $w_1,w_2,\ldots,w_k$。依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问。 这时候我们需要利用队列来保证我们访问节点的顺序，此时我们的效率比深搜大大提高，原因是我们能够省去很多的重复步骤，程序架构如下： ```cpp void bfs(){ 定义队列 q; q.push(初始状态); while(队不空){ x(y)=队头状态信息; 出队; if(下一步可行)下一步; } } ``` 【例题】[P1451 求细胞数量](https://www.luogu.com.cn/problem/P1451) ```cpp struct grid{ int x,y; }; queue<struct grid> q; void BFS(){ cnt++; while(!q.empty()){ int x=q.front().x; int y=q.front().y; vis[x][y]=1; q.pop(); for(int i=0;i<4;i++){ int xx=x+dx[i],yy=y+dy[i]; if(yy<m&&xx<n&&xx>=0&&yy>=0){ if(!vis[xx][yy]&&p[xx][yy]!='0'){ q.push({xx,yy}); } } } } return; } ``` 【例题】[AT1350 深さ優先探索](https://www.luogu.com.cn/problem/AT1350) ```cpp struct grid{ int x,y; }; bool check(int x,int y){ return (!vis[x][y]&&x>=1&&x<=n&&y>=1&&y<=m); } void bfs(){ queue<grid>q; q.push({x,y}); while(!q.empty()){ int xx=q.front().x,yy=q.front().y; q.pop(); vis[xx][yy]=1; if(check(xx+1,yy))q.push({xx+1,yy}); if(check(xx,yy+1))q.push({xx,yy+1}); if(check(xx-1,yy))q.push({xx-1,yy}); if(check(xx,yy-1))q.push({xx,yy-1}); } } ``` ## 优化：剪枝/记忆化搜索 ~~常言道：记搜+剪枝可以解决一切问题~~ 记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。 **记忆化搜索：** 而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。 **剪枝：** - 可行性剪枝 当目前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判断不可行，直接返回。 - 排除等效冗余 当几个字树具有完全相同的效果的时候，只选择其中一个搜索。 - 最优性剪枝 在我们用搜索方法解决最优化问题的时候的一种常用剪枝。当搜索还未结束时，记录的状态已经比当前保存的最优解更劣，那么此方案一定无效，停止搜索并回溯即可。 - 顺序剪枝 普遍来讲，搜索的顺序是不固定的，对一个问题来说，算法可以进入搜索树的任意的一个子节点。 但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。 此剪枝一定优先按照题目要求！ ## 题目组成 - [P1331 海战](https://www.luogu.com.cn/problem/P1331) - [P1087 [NOIP2004 普及组] FBI 树](https://www.luogu.com.cn/problem/P1087) - [P1596 [USACO10OCT]Lake Counting S](https://www.luogu.com.cn/problem/P1596) - [P1141 01迷宫](https://www.luogu.com.cn/problem/P1141) - [CF1059B Forgery](https://www.luogu.com.cn/problem/CF1059B) - [P1451 求细胞数量](https://www.luogu.com.cn/problem/P1451) - [SP15436 UCV2013H - Slick](https://www.luogu.com.cn/problem/SP15436) - [AT46 リモコン](https://www.luogu.com.cn/problem/AT46) - [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) - [P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins ](https://www.luogu.com.cn/problem/P1460) - [P1030 [NOIP2001 普及组] 求先序排列](https://www.luogu.com.cn/problem/P1030) - [P1706 全排列问题](https://www.luogu.com.cn/problem/P1706) - [AT1350 深さ優先探索](https://www.luogu.com.cn/problem/AT1350) - [P1123 取数游戏](https://www.luogu.com.cn/problem/P1123) - [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443) - [P1747 好奇怪的游戏](https://www.luogu.com.cn/problem/P1747) - [P3915 树的分解](https://www.luogu.com.cn/problem/P3915) - [P3956 [NOIP2017 普及组] 棋盘](https://www.luogu.com.cn/problem/P3956) - [P1219 [USACO1.5]八皇后 Checker Challenge](https://www.luogu.com.cn/problem/P1219) - [P4961 小埋与扫雷](https://www.luogu.com.cn/problem/P4961) - [CF1063B Labyrinth](https://www.luogu.com.cn/problem/CF1063B) - [P1294 高手去散步](https://www.luogu.com.cn/problem/P1294) - [UVA439 骑士的移动 Knight Moves](https://www.luogu.com.cn/problem/UVA439) - [P1025 [NOIP2001 提高组] 数的划分](https://www.luogu.com.cn/problem/P1025) - [UVA572 油田 Oil Deposits](https://www.luogu.com.cn/problem/UVA572) - [UVA102 Ecological Bin Packing](https://www.luogu.com.cn/problem/UVA102) - [CF659E New Reform](https://www.luogu.com.cn/problem/CF659E) - [CF55B Smallest number](https://www.luogu.com.cn/problem/CF55B) - [P1144 最短路计数](https://www.luogu.com.cn/problem/P1144) - [UVA532 Dungeon Master](https://www.luogu.com.cn/problem/UVA532) --------- 这一份题单在暴力搜索的同时也有部分剪枝和优化内容。 ## 其他内容