# 前置知识
可以通过这篇回溯攻略，先了解一下深度优先搜索的决策树以及工作流程。
可以通过这篇文章了解矩阵中坐标向其他方向扩散的实现方式。
# DFS 与 BFS
他们是两种不同的搜索方式，非常相似，以至于很多问题都是用哪种都可以。但是因为搜索顺序的不同，又有些许不同的点：
- 空间占用 BFS 较多，DFS 较少。BFS 是按照层搜索，一般的实现方式是使用队列，极端情况下队列中会存放非常多的数据，但是 DFS 一般使用递归实现，因此相较于 BFS 使用的空间就少很多了。
- DFS 可能出现 “爆栈” 的情况，也就是系统栈不够用。DFS 的实现方式是递归，那我们都知道递归是使用系统栈来存放每层的数据，如果层数过深必然会出现 “爆栈” 现象。
- BFS 可以搜索 “最小”、“最短” 等极值情况，DFS 一般认为不可以。
# DFS 的常规思路
DFS 的递归函数一般可以简单的理解为由两个基础部分组成：
- 递归终止条件。
- 递归整体逻辑。
dfs() { | |
if (递归终止条件) return ; | |
递归整体逻辑 | |
} |
我们依旧从最简单的基础问题作为切入点，初步探究 DFS 的最基础思路。
# AcWing 1112. 迷宫
一天 Extense 在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有 2 种状态，. 和 #，前者表示可以通行后者表示不能通行。
同时当 Extense 处在某个格点时，他只能移动到东南西北 (或者说上下左右) 四个方向之一的相邻格点上，Extense 想要从点 A 走到点 B，问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行 (为 #)，则看成无法办到。
注意：A、B 不一定是两个不同的点。
输入格式
第 1 行是测试数据的组数 k，后面跟着 k 组输入。每组测试数据的第 1 行是一个正整数 n，表示迷宫的规模是 n∗n 的。
接下来是一个 n∗n 的矩阵，矩阵中的元素为。或者 #。
再接下来一行是 4 个整数 ha,la,hb,lb，描述 A 处在第 ha 行，第 la 列，B 处在第 hb 行，第 lb 列。
注意到 ha,la,hb,lb 全部是从 0 开始计数的。
输出格式
k 行，每行输出对应一个输入。能办到则输出 “YES”，否则输出 “NO”。
数据范围
1≤n≤100输入样例
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0输出样例
YES NO
# 题目描述
题目很好理解，给出一个二维矩阵，从一个起始点开始移动，为 “.” 的坐标可以走，为 “#” 的坐标不能走，问最后能否有办法移动到终点。
# 题目分析
很容易发现，本题是一个求连通性的问题，其本质是问 起始点与目标点是否连通。
如此，就可以得到这题的思路，我们从起始点不断的搜索，只要是可以通过的点就一直走下去，如果与目标点是连通的，那么我们迟早可以搜索到这个目标点，如果我们把所有的连通点都搜索完毕之后，还是没找到目标点，说明与目标点不连通。
# Code
递归函数的含义：当前坐标可以扩散到的点中是否有目标点。
因此，参数必须有当前坐标的点 {x, y}。
#include <iostream> | |
#include <cstring> | |
using namespace std; | |
const int N = 110; | |
bool st[N][N]; | |
char g[N][N]; | |
int n, sa, sb, ea, eb; | |
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; | |
bool dfs(int x, int y) { | |
// 当前坐标不可通过 | |
if (g[x][y] == '#') return false; | |
// 递归终止条件 找到目标点 | |
if (x == ea and y == eb) return true; | |
// 因为坐标是向四个方向扩散 所以需要避免坐标重复使用 | |
st[x][y] = true; | |
for (int i = 0; i < 4; i ++ ) { | |
int a = x + dx[i], b = y + dy[i]; | |
if (a < 0 or a >= n or b < 0 or b >= n) continue; | |
// 核心递归函数 如果下一个连通点没有使用 则扩展过去 | |
// 判断下一个连通点 是否可以扩展到目标点 | |
if (!st[a][b] and dfs(a, b)) return true; | |
} | |
// 最后所有点都扩展完 则返回 false | |
return false; | |
} | |
int main() { | |
int T; | |
cin >> T; | |
while (T -- ) { | |
memset(st, 0, sizeof st); | |
cin >> n; | |
for (int i = 0; i < n; i ++ ) | |
for (int j = 0; j < n; j ++ ) | |
cin >> g[i][j]; | |
cin >> sa >> sb >> ea >> eb; | |
if (dfs(sa, sb)) puts("YES"); | |
else puts("NO"); | |
} | |
} |
# 模板扩展
基于本题，找一下规律，我们来看看 DFS 的核心基础部件都有哪些。
函数的参数。本题函数的参数是由坐标点构成的，这是因为在递归的过程中，我们需要使用坐标来标记扩散到的点。因此，可以暂时认为函数的参数与每层的状态有关。即，下一层的坐标是 {a, b}，那么我们就要让这个坐标通过参数传递。
递归的终止条件。递归终止条件一般是比较容易发现的，比如：对于本题，终止条件就是传入的参数等于目标点，说明我们找到了目标，这时候就可以结束递归了。因此，可以暂时认为递归的终止条件，通常可以较为简单的在题目描述中发现。
最难的判重数组。判重数组的作用很简单，防止数据被重复使用。比如在本题中，坐标是向四个方向扩散，如果当前坐标向下扩散到下一个坐标，而下一个坐标向上扩散又回到了当前坐标，这当然是不行的，所以我们用判重数组，把当前坐标加到判重数组里，在下一个坐标扩散的时候，向上扩散到了当前坐标，发现在判重数组中，就可以直接跳过。因此，可以暂时的认为是否需要使用判重数组，需要观察在递归的过程中，有没有可能重复使用数据。
从递归的整体性上去考虑，或许会简单很多。很多 DFS 的相关文章都没有提到这一点。我们可以先从整体性上去考虑递归函数的含义，比如，在本题中，递归函数的整体含义是判断参数坐标是否可以扩展到目标点。 这样，自然的就可以理解把扩展到的点传给函数的意义，也就是判断扩展到的点能否扩展到目标点。 如果可以的话，当前点就是与目标点连通的。也就是，
a->b + b->c ==> a->b->c。因此，在完成递归搜索之前，可以优先考虑递归函数的整体含义是什么。
# AcWing 1113. 红与黑
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。当在一行中读入的是两个零时，表示输入结束。
输出格式
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数 (记数时包括初始位置的瓷砖)。数据范围
1≤W,H≤20输入样例
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0输出样例
45
# 题目描述
与上题比较类似，给出一个二维矩阵，以及一个初始点，判断矩阵中有多少坐标是与初始点连通的。
# 题目分析
把我们的模板用上，根据上题变形一下递归含义。
递归函数的含义变成：求当前节点能扩展到几个连通点。
并且，我们很容易发现，当前节点总共能扩展到多少连通点，是由他所能扩展到的四个方向上的点确定的。换句话理解，把 与当前坐标 所连通的其他坐标 可以连通的点个数 都加起来，就是当前坐标所能扩展到的所有点个数。
# Code
递归函数的含义是：有多少点与当前点连通。
#include <iostream> | |
#include <cstring> | |
using namespace std; | |
const int N = 22; | |
int n, m; | |
int sa, sb; | |
char g[N][N]; | |
bool st[N][N]; | |
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; | |
// 参数的含义是 点的坐标 {x, y} | |
int dfs(int x, int y) { | |
// 当前点 自己与自己连通 算一个连通点。 | |
int res = 1; | |
// 因为是四个方向的扩展 所以需要判重。 | |
st[x][y] = true; | |
for (int i = 0; i < 4; i ++ ) { | |
int a = x + dx[i], b = y + dy[i]; | |
if (a < 0 or a >= n or b < 0 or b >= m) continue; | |
if (g[a][b] != '.') continue; | |
// 把 与当前连通的点的全部连通点个数加起来 | |
// 就是当前点的连通个数。 | |
if (!st[a][b]) res += dfs(a, b); | |
} | |
return res; | |
} | |
int main() { | |
while (cin >> m >> n, m and n) { | |
memset(st, 0, sizeof st); | |
for (int i = 0; i < n; i ++ ) | |
for (int j = 0; j < m; j ++ ) { | |
cin >> g[i][j]; | |
// 读取数据的同时 确定起始点坐标 | |
if (g[i][j] == '@') sa = i, sb = j; | |
} | |
cout << dfs(sa, sb) << endl; | |
} | |
return 0; | |
} |
# AcWing 1116. 马走日
马在中国象棋以日字形规则移动。
请编写一段程序，给定 n∗m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
输入格式
第一行为整数 T，表示测试数据组数。每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y。
输出格式
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，若无法遍历棋盘上的所有点则输出 0。数据范围
1≤T≤9, 1≤m,n≤9, 1≤n×m≤28, 0≤x≤n−1, 0≤y≤m−1输入样例
1 5 4 0 0输出样例
32
# 题目描述
给出一个二维矩阵，给出一个起始点，按照象棋的方式移动，问有多少种方案可以走遍矩阵中的所有点。
# 题目分析
本题需要在所有点都遍历完之后才可以算找到一个方案，因此，需要一个递归函数外部的变量统计方案数。递归终止条件则为棋盘上所有点都遍历完成。
如何确保遍历到所有的方案呢？答案是使用回溯。有关回溯，可以参考：回溯攻略。
# Code
有一个关键点需要注意，因为我们要知道当前遍历了多少点，用以判断是否找到一个方案，所以递归参数除了坐标外，还要增加一个遍历点的数量，这样当遍历的点达到棋盘大小的时候，说明找到一个方案。
#include <iostream> | |
#include <cstring> | |
using namespace std; | |
const int N = 30; | |
int n, m, sx, sy; | |
bool st[N][N]; | |
int res; // 使用全局变量统计结果 | |
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; | |
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; | |
//cnt 表示当前已经遍历了多少点。 | |
void dfs(int x, int y, int cnt) { | |
// 递归终止条件 | |
if (cnt == n * m) { | |
res += 1; | |
return ; | |
} | |
st[x][y] = true; | |
for (int i = 0; i < 8; i ++ ) { | |
int a = x + dx[i], b = y + dy[i]; | |
if (a < 0 or a >= n or b < 0 or b >= m) continue; | |
if (!st[a][b]) dfs(a, b, cnt + 1); | |
} | |
st[x][y] = false; // 回溯 | |
} | |
int main() { | |
int T; | |
cin >> T; | |
while (T -- ) { | |
memset(st, 0, sizeof st); | |
res = 0; | |
cin >> n >> m >> sx >> sy; | |
dfs(sx, sy, 1); | |
cout << res << endl; | |
} | |
return 0; | |
} |
# 模板扩展
本题有一个和上两道题明显不一样的地方，在于本题有一个回溯的动作。有关回溯的使用，我们已经在一篇单独的文章中有所讲解。在本文中，主要想说明的是：在什么时候应该回溯，而什么时候不需要回溯。
本题大致的决策树如下：
而前两题的决策树如下：
可以看到比较明显的差别是，本题的决策中，需要向回搜索，而前两题的搜索中，都是一条道走到黑不用回头的。
所以，我们暂时可以认为，当在搜索的过程中需要 “往回走” 的时候，使用回溯。
# AcWing 1117. 单词接龙
单词接龙是一个与我们经常玩的成语接龙相类似的游戏。
现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的 “龙”，每个单词最多被使用两次。
在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。
我们可以任意选择重合部分的长度，但其长度必须大于等于 1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。
输入格式
输入的第一行为一个单独的整数 n 表示单词数，以下 n 行每行有一个单词（只含有大写或小写字母，长度不超过 20），输入的最后一行为一个单个字符，表示 “龙” 开头的字母。你可以假定以此字母开头的 “龙” 一定存在。
输出格式
只需输出以此字母开头的最长的 “龙” 的长度。数据范围
n≤20输入样例
5 at touch cheat choose tact a输出样例
23提示
连成的“龙”为 atoucheatactactouchoose。
# 题目描述
给出一些单词，有些单词首尾具有重合部分，这样的词，我们可以拼接在一起，拼接后的新单词共用重合部分。目的是 找到可以通过拼接得到的最长的单词的长度。（每个单词可以使用两次。）
# 题目分析
我们的目标是求出最长的长度，那么显然可以枚举所有可行的拼接情况，找出拼接后最长的单词即可。
那么如何进行单词的拼接呢？
我们可以递归的对每个单词 都判断与单词龙的末尾 是否有公共部分，如果有，就可以把该单词公共部分之后的字符拼接到单词龙。
为了快速找到公共部分，可以预先处理出所有单词两两之间的关系，即，他们的前后缀公共部分的长度。
# Code
对于递归的参数，我们需要传入两个：
- 一个是当前的单词龙，用来实时更新最长的长度；
- 一个是当前的单词龙是以哪个单词为结尾的，用来判断哪个单词可以继续拼接到当前单词龙后面。
我们每次递归都会对所有单词判断是否可以拼接，并且每个单词只能使用两次，所以必须要判重数组，来判断枚举到的单词能不能用。
是否需要回溯？
考虑这样的场景，有 A、B 两个单词都可以接到当前单词龙的后面，那我们处理完 A 之后，一定要再回到当前单词龙，接着处理 B ，所以需要回溯。
#include <iostream> | |
#include <cstring> | |
#include <algorithm> | |
using namespace std; | |
const int N = 22; | |
int n; | |
string w[N]; | |
int res; // 全局变量记录结果 | |
int st[N]; | |
int mp[N][N]; // 存储两个单词之间的公共部分长度 | |
char start; | |
//s 表示当前的字符串龙 i 表示字符串的末尾是哪个单词。 | |
void dfs(string s, int i) { | |
res = max(res, (int)s.size()); | |
st[i] += 1; | |
for (int j = 0; j < n; j ++ ) { | |
if (st[j] < 2 and mp[i][j]) { | |
dfs(s + w[j].substr(mp[i][j]), j); | |
} | |
} | |
st[i] -= 1; | |
} | |
// 初始化 所有单词 两两之间的公共部分长度 | |
void init() { | |
for (int i = 0; i < n; i ++ ) | |
for (int j = 0; j < n; j ++ ) { | |
string a = w[i], b = w[j]; | |
for (int k = 1; k < min(a.size(), b.size()); k ++ ) { | |
if (a.substr(a.size() - k, k) == b.substr(0, k)) { | |
mp[i][j] = k; | |
break; | |
} | |
} | |
} | |
} | |
int main() { | |
cin >> n; | |
for (int i = 0; i < n; i ++ ) cin >> w[i]; | |
init(); | |
cin >> start; | |
// 枚举所有可行的拼接 | |
for (int i = 0; i < n; i ++ ) { | |
if (w[i][0] == start) dfs(w[i], i); | |
} | |
cout << res << endl; | |
return 0; | |
} |
# AcWing 1118. 分成互质组
给定 n 个正整数，将它们分组，使得每组中任意两个数互质。
至少要分成多少个组？
输入格式
第一行是一个正整数 n。第二行是 n 个不大于 10000 的正整数。
输出格式
一个正整数，即最少需要的组数。数据范围
1≤n≤10输入样例
6 14 20 33 117 143 175输出样例
3
# 题目描述
给出一个数组，将他们分组，要求每个组中任意两个数都是互质的，问最少需要多少组。
# 题目分析
枚举所有的分组方案，自然可以找出分组数最少的。那么我们就需要选择一个搜索顺序来保证所有可行的分组方案全被遍历过。
本题里，我们选择的顺序是枚举当前组能否装下的未分配的数，一旦遇到某个数不可以被装到当前组中，就新开一个组，按照这种顺序，我们一定可以保证正确的枚举了所有可行的分组情况。
好比，有很多苹果要放到一些篮子里面，我们拿着一个篮子，去把能放的放进来，最后如果有不能放的，我们就再拿一个篮子，重新从第一个开始再放一遍，如果还有未选择的苹果，就再拿一个篮子，如此往复，我们一定能保证最后所有的苹果都装在篮子里。
# Code
根据上面思路，很明显的我们要传的参数是：
- 当前正在使用的是哪个组；
- 当前组放了几个数，用于判断某个数，是否与当前组的所有数都互质；
- 当前已经分配了多少个数，用来判断递归终止条件；
- 当前组分配到了第几个数，避免当前组每次都从头开始。
是否需要判重？
每个元素只能使用一次，当选择一个新分组的时候，我们要重新从第一个开始枚举，以找到所有未放到前面分组的数，而这时，使用过的数，不可重复放入。所以必须有一个判重数组，来存储已经使用的数。
是否需要回溯？
很显然需要，因为每个数字放到某组之后，并不是就不动了，它很有可能还能放到其他组，我们的目的是为了搜索出所有的可行分组，需要回溯。
#include <iostream> | |
using namespace std; | |
const int N = 11; | |
int p[N]; | |
bool st[N]; | |
int group[N][N]; | |
int n, res = N; // 最多的分组情况 每个数字占一组 | |
// 欧几里德算法判断两个数是否互质 | |
int gcd(int a, int b) { | |
return b ? gcd(b, a % b) : a; | |
} | |
// 判断 i 和当前组内的所有元素是否都互质 | |
bool check(int group[], int gc, int i) { | |
for (int j = 0; j < gc; j ++ ) { | |
if (gcd(p[group[j]], p[i]) > 1) return false; | |
} | |
return true; | |
} | |
//g 表示 第几组 | |
//gc 表示 当前组内的下标 | |
//tc 当前总共安排了多少个元素 | |
//start 当前从哪个元素开始搜 | |
void dfs(int g, int gc, int tc, int start) { | |
// 当前组的数量 大于等于 res 说明不是最优解 | |
if (g >= res) return ; | |
bool flag = true; | |
// 搜过的元素数量到达 n 则说明搜到一种结果 | |
if (tc == n) res = g; //g 一定小于 res 所以直接更新最优解 | |
for (int i = start; i < n; i ++ ) { | |
//i 没有用过 并且 和 g 组的所有元素都互质 | |
if (!st[i] and check(group[g], gc, i)) { | |
st[i] = true; | |
group[g][gc] = i; // 放到 g 组的 gc 这个位置 | |
dfs(g, gc + 1, tc + 1, i + 1); // 下一层 | |
st[i] = false; | |
flag = false; // 可以放到 g 组 不需要新开组 | |
} | |
} | |
if (flag) dfs(g + 1, 0, tc, 0); //flag 为 1 需要新开一个组 g+1 | |
} | |
int main() { | |
cin >> n; | |
for (int i = 0; i < n; i ++ ) cin >> p[i]; | |
dfs(1, 0, 0, 0); | |
cout << res << endl; | |
return 0; | |
} |
欲知后事如何，且听下回分解
