「JY/DFS - Part I」

- **[Part I](https://www.luogu.com.cn/training/78649)** - [Part II](https://www.luogu.com.cn/training/98480) --- dfs 是经典的递归算法之一，是学习搜索算法最重要的一环。 本题单适合初学者练习，熟练 dfs 的也可以用此题单巩固。 注：本题单大多为普通、剪枝、折半 dfs，对 IDA\* 、记忆化不会进行过多的赘述。 --- 下面是 dfs 的一些经典题型。 ### 一、迷宫 - 连通块 这些是用 dfs 求连通块的题目，可以初步了解 dfs。 | 题目 | 做法提示 | | :----------: | :----------: | | [P1451 求细胞数量](https://www.luogu.com.cn/problem/P1451) | 四向连通块，将 `0` 视为墙壁 | | [P1596 \[USACO10OCT\]Lake Counting S](https://www.luogu.com.cn/problem/P1596) | 八向连通块 | | [P1683 入门](https://www.luogu.com.cn/problem/P1683) | 连通块大小计数，我们可以先 dfs 一遍，然后把标记过的地方全加起来 | | [P1162 填涂颜色](https://www.luogu.com.cn/problem/P1162) | 我们可以将不在图形内的 `0` 全部标记一遍，没标记的就是要填涂的 | | [P1331 海战](https://www.luogu.com.cn/problem/P1331) | 其中一种判断矩阵的方法：记录每个连通块的左上、左下、右上、右下四个点进行比较 | | [P1183 多边形的面积](https://www.luogu.com.cn/problem/P1183) | 利用毕克定理遍历格点数 | ### 二、数据较小的 01 背包 dfs 是一种递归思想，我们可以通过一些数据较小的题目来初步了解 01 背包，同时巩固递归算法。 | 题目 | 做法提示 | | :----------: | :----------: | | [P1049 \[NOIP2001 普及组\] 装箱问题](https://www.luogu.com.cn/problem/P1049) | 设置 dfs 参数 $s$，其表示当前所使用的重量，每次可选择不装/装得下 $v_{dep}$ 时装，最后 $dep>n$ 时比较 $v-s$ | | [P1060 \[NOIP2006 普及组\] 开心的金明](https://www.luogu.com.cn/problem/P1060) | 与上一题类似，仅需修改每次 $s$ 增加的值 | | [P1460 \[USACO2.1\]健康的荷斯坦奶牛 Healthy Holsteins](https://www.luogu.com.cn/problem/P1460) | 用 $ans$ 数组存答案，$c$ 数组作当前状态答案，同时用 `f(x)` 去判定是否符合要求 | ### 三、迷宫 - 方案数 前面我们已经通过 dfs 染色法求连通块有了一定的认识。我们可以在此基础上来学习迷宫问题的方案数问题。 | 题目 | 做法提示 | | :----------: | :----------: | | [P1605 迷宫](https://www.luogu.com.cn/problemnew/show/P1605) | 用 $f$ 数组标记是否走过（注意搜完后要重新变成未走过状态，即下面说到的回溯），障碍与走过的点可以同时视为不可走过（即直接将障碍点 $f_{x,y}$ 变为 $1$） | | [P1644 跳马问题](https://www.luogu.com.cn/problem/P1644) | 对于“马”的走法，在本题中不可往回走，因此为 $x±[1,2],y+[1,2]$，每次满足要求就加一 | | [P1101 单词方阵](https://www.luogu.com.cn/problem/P1101) | 这题要对于每一个点都进行一次扩展 | | [P1238 走迷宫](https://www.luogu.com.cn/problem/P1238) | 这题我们可以用 `pair<int,int>ans[];` 来记录答案 | ### 四、迷宫 - 最短/长路 有了方案数，我们就可以来求迷宫的最短/长路。 但可悲的是，dfs 求最短路权值最小路的题目已经逐渐减少，大多数题目需 bfs 和 dp，所以给出的题目大多都需要卡时技巧或记忆化。 | 题目 | 做法提示 | | :----------: | :----------: | | [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443) | 这题使用 dfs 时限较紧，需要减少一次递归，同时最大数据为 $n=m=400$，每个点最大答案为 $400\div3\times4≈532$ 步，$dep$ 大于该数直接退出本次搜索 | | [P3956 \[NOIP2017 普及组\] 棋盘](https://www.luogu.com.cn/problem/P3956) | 这题需要好好想一下如何处理大量的判断与累加 | | [P7074 \[CSP-J2020\] 方格取数](https://www.luogu.com.cn/problem/P7074) | 这题需要记忆化 | ### 五、剪枝 & 回溯 剪枝与回溯是 dfs 的精髓。 这些题目中有些综合性较强。 | 题目 | 做法提示 | | :----------: | :----------: | | [P1157 组合的输出](https://www.luogu.com.cn/problem/P1157) | 排列组合，每次循环遍历每个数是否排进去了，若非则加入 $a$ 数组并标记再进行搜索，搜完后回溯标记（当然，你可以记一个 $lst$，这样每次就只会从 $lst+1$ 开始搜，无需标记） | | [P2404 自然数的拆分问题](https://www.luogu.com.cn/problem/P2404) | 每次可拆 $1\sim \texttt{\small 当前的}n$ 之间的数，每次拆完时输出一个方案 | | [P1025 \[NOIP2001 提高组\] 数的划分](https://www.luogu.com.cn/problem/P1025) | 有个数限制的自然数拆分 | | [P1036 \[NOIP2002 普及组\] 选数](https://www.luogu.com.cn/problem/P1036) | 每次可选$a_{\texttt{\small 当前的}i\sim n}$ 之间的数,选完后进行判素数 | | [P1218 \[USACO1.5\]特殊的质数肋骨 Superprime Rib](https://www.luogu.com.cn/problem/P1218) | 每次添加一个数并即时判断是否为质数，是则继续搜 | | [P1019 \[NOIP2000 提高组\] 单词接龙](https://www.luogu.com.cn/problem/P1019) | $f_i$ 记录使用次数；每次搜索时都更新答案 | | [UVA124 Following Orders](https://www.luogu.com.cn/problem/UVA124) | 有约束性的排列组合 | | [P2040 打开所有的灯](https://www.luogu.com.cn/problem/P2040) | 记 $ans$ 为最少步数，关键性的剪枝：若 $dep>ans$ 且还未结束开关灯，则直接退出 | | [P2819 图的m着色问题](https://www.luogu.com.cn/problem/P2819) | 我们直接使用邻接矩阵存储连接关系，然后符合条件就继续搜索 | | [P2327 \[SCOI2005\]扫雷](https://www.luogu.com.cn/problem/P2327) | 其实更像背包，令 $a_i$ 表示雷是否摆放在 $i$ 处，$b$ 表示输入的数组，剪枝：只有 $a_{dep-2}+a_{dep-1}+a_{dep}=b_{dep-1}$ 才能继续递归 | | [P1219 \[USACO1.5\]八皇后 Checker Challenge](https://www.luogu.com.cn/problem/P1219) | 更像排列组合（行列就处理完了），需要想好判断斜线的方法 | | [P1784 数独](https://www.luogu.com.cn/problem/P1784) | 用 $h,l,g$ 分别表示行、列、宫，每次对于每个空的地方填 $1\sim9$（非空就继续走下一个格子），直到 $x=y=9$ | | [P1043 \[NOIP2003 普及组\] 数字游戏](https://www.luogu.com.cn/problem/P1043) | 这题需要像环形区间 dp 的办法一样进行“破环为链”，另外负数对 $10$ 取模的操作为 $((n\bmod10)+10)\bmod10$ | | [P1236 算24点](https://www.luogu.com.cn/problem/P1236) | 这题要对于每个符号、每个数字进行排列组合，剪枝：在 $s<0$ 或 $dep>4$ 但 $s\neq24$ 时直接退出 | | [P1562 还是N皇后](https://www.luogu.com.cn/problem/P1562) | 本题需要位运算的优化 | | [P1120 小木棍](https://www.luogu.com.cn/problem/P1120) | 本题需要大量的剪枝 | | [P1380 T型骨牌](https://www.luogu.com.cn/problemnew/show/P1380) | 本题需要对其 $n\times m$ 的搜索变成 $(n-2)\times(m-2)$（注意特判 $n<3$ 或 $m<3$），同时每次减少一次递归以减少时间 | ### 六、折半 dfs 运用折半搜索（$\texttt{Meet-in-Middle}$），可以将 $O(k^n)$ 变为 $O(k^{\frac{n}{2}})$。 | 题目 | 做法提示 | | :----------: | :----------: | | [CF888E Maximum Subsequence](https://www.luogu.com.cn/problem/CF888E) | 对于 $1\sim\frac{n}{2}$ 和 $\frac{n}{2}\sim n$ 分别进行计算答案，然后用 $\texttt{two-pointers}$ 算法找出答案 | | [P4799 \[CEOI2015 Day2\] 世界冰球锦标赛](https://www.luogu.com.cn/problem/P4799) | 同样，需要折半 |