深搜其实用的就是栈，虽然不是手写的栈，但是递归函数就是在调用系统的栈。

dfs基础篇

（1）排列数字

#include<cstdio>
int N;
int path[15], vis[15];
void dfs(int u) {if (u == N) {for (int i = 0; i < N; i++) printf("%d%c", path[i], i + 1 == N ? '\\n' : ' ');return;}for (int i = 1; i <= N; i++) {if (!vis[i]) {path[u] = i;vis[i] = true;dfs(u + 1);vis[i] = false;}}
}
int main() {scanf("%d", &N);dfs(0);return 0;
}

（2）n-皇后问题

• 副对角线从右往左编号，主对角线从左往右编号。对角线均从0开始编号
• 这道题其实难在寻找对角线的编号与行、列之间的关系。这个关系其实与编号方式有关，并不唯一。这里展现的是我自己按照上述规则编号然后写的代码，和大雪菜的不完全相同。

#include<cstdio>
int col[20], dg[20], udg[20], N;
char G[20][20];//皇后的位置记为'Q'，空白的位置记为'.'
void dfs(int u) {if (u == N) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) printf("%c", G[i][j]);printf("\\n");}printf("\\n");return;}for (int j = 0; j < N; j++) {//看看列，主对角线，副对角线是否冲突。if (!col[j] && !udg[u + j] && !dg[u - j + N - 1]) {G[u][j] = 'Q';col[j] = udg[u + j] = dg[u - j + N - 1] = true;dfs(u + 1);//回溯，即恢复到原始状态。col[j] = udg[u + j] = dg[u - j + N - 1] = false;G[u][j] = '.';}}
}
int main() {scanf("%d", &N);for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) G[i][j] = '.';}dfs(0);return 0;
}

dfs提高篇

连通性

1112. 迷宫

• 仔细想想，这道题其实可以不用回溯，就是不用还原状态。因为不管往哪个方向去搜，之前行径都是一样的。简而言之，内部搜索不需要恢复状态，但是外部搜索是把整个棋盘当作一个状态。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 110;
char mz[maxn][maxn];
int N, sx, sy, tx, ty, dx[] = { 1, -1, 0, 0 }, dy[] = {0, 0, 1, -1};
bool vis[maxn][maxn];
bool dfs(int x, int y) 
{if (mz[x][y] == '#') return false;if (x == tx && y == ty) return true;vis[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;if (vis[nx][ny]) continue;if (dfs(nx, ny)) return true;}return false;
}
int main() {int T;scanf("%d", &T);while (T--) {scanf("%d", &N);memset(vis, false, sizeof vis);for (int i = 0; i < N; i++) {scanf("%s", mz[i]);}scanf("%d%d%d%d", &sx, &sy, &tx, &ty);if (dfs(sx, sy)) printf("YES\\n");else printf("NO\\n");}return 0;
}

剪枝与优化

• 剪枝常见策略：

1. 优化搜索顺序：大部分情况下,我们应该优先搜索分支较少的节点。
2. 排除等效冗余
3. 可行性剪枝：一个方案不可行的话就剪掉
4. 最优性剪枝：一旦确定一个解不是最优解就减掉。

165. 小猫爬山

• $n$ 只小猫，第 $i$ 只小猫的重量是 CiC_iCi​，一个缆车的承重量为 $W$，问最少需要多少缆车？

• 先放重的猫，可以使后面的分支较少。具体怎么剪枝看注释。

• 他这次的思路是把小猫往每个车上都放一下，dfs，然后再拿下来。

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
const int maxn = 25;
int sum[maxn], w[maxn], N, W, ans = 18;
void dfs(int u, int k) {//最优性剪枝if (k >= ans) return;if (u == N) {ans = k;return;}for (int i = 0; i < k; i++) {if (sum[i] + w[u] <= W) {  //可行性剪枝sum[i] += w[u];dfs(u + 1, k);sum[i] -= w[u];}}sum[k] = w[u];dfs(u + 1, k + 1);sum[k] = 0;
}
int main() {scanf("%d%d", &N, &W);for (int i = 0; i < N; i++) scanf("%d", &w[i]);//优化搜索顺序sort(w, w + N, greater<int>());dfs(0, 0);printf("%d\\n", ans);return 0;
}

166. 数独

• 有状态压缩的感觉，每行每列每个小的9宫格，都用一个9位的二进制数字来表示。然后，再用ones数组储存1个数，再用一个数组储存以2为底的对数值。
• 设计四个辅助函数：

1. 初始化函数init：把每行每列每个小九宫格的状态都初始化为9个1，表示9个数字都没有被使用。
2. 填数字与拿下数字的函数
3. lowbit函数
4. 获得行、列、9宫格的交，表示还可以填上哪些数字。

• 关于剪枝：一开始要从分支数量最少的开始搜索，也就是说从1最少的状态开始深搜。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 9;
char str[100];
int ones[1 << N], map[1 << N], col[N], row[N], cel[3][3];
void init() {for (int i = 0; i < N; i++) col[i] = row[i] = (1 << N) - 1;for (int i = 0; i < 3; i++) {for (int j = 0; j < 3; j++) {cel[i][j] = (1 << N) - 1;}}
}
void draw(int x, int y, int t, bool is_set) {if (is_set) str[x * N + y] = '1' + t;else str[x * N + y] = '.';int v = 1 << t;if (!is_set) v = -v;row[x] -= v;col[y] -= v;cel[x / 3][y / 3] -= v;
}
int lowbit(int x) {return x & -x;
}
int get(int x, int y) {return row[x] & col[y] & cel[x / 3][y / 3];
}
bool dfs(int cnt) {if (cnt == 0) return true;int minv = 10;//优化搜索顺序int x, y;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (str[i * N + j] != '.') continue;int state = get(i, j);if (ones[state] < minv) {x = i, y = j;minv = ones[state];}}}int state = get(x, y);//printf("%d ### \\n", state);for (int i = state; i; i -= lowbit(i)) {int t = map[lowbit(i)]; //这个其实就是快速找到最后一个1的位置，不用按位与运算了。//printf("%d *** \\n", t);draw(x, y, t, true);if (dfs(cnt - 1)) return true;draw(x, y, t, false);}return false;
}
int main() {for (int i = 0; i < N; i++) map[1 << i] = i;for (int i = 0; i < 1 << N; i++) {for (int j = 0; j < N; j++) {if (i >> j & 1) ones[i]++;}}while (cin >> str, str[0] != 'e') {init();int cnt = 0;for (int i = 0, k = 0; i < N; i++) {for (int j = 0; j < N; j++, k++) {if (str[k] == '.') cnt++;else {draw(i, j, str[k] - '1', true);}}}dfs(cnt);cout << str << endl;}
}

迭代加深

• 迭代加深搜索适用于这样的：在搜索树中，答案不会很深，但是错误的答案可能比较深。因此可以设置一个max_depth，超过这个就意味着可以剪掉了。
• 可以从1开始枚举depth。一般来讲，depth代表能到的最大的搜索层数，一旦超过就 return false.

170. 加成序列

满足如下条件的序列 $X$（序列中元素被标号为 $1、2、3,...,m$）被称为“加成序列”：

1. $X[1]=1$
2. $X[m]=n$
3. $X[1]\le X[2]\le ...\le X[m-1]\le X[m]$
4. 对于每个 $k(2\le k\le m)$ 都存在两个整数 $i$ 和 $j$ ($1\le i,j\le k-1$, $i$ 和 $j$ 可相等），使得 $X[k]=X[i]+X[j]$。

你的任务是：给定一个整数 $n$，找出符合上述条件的长度 $m$ 最小的“加成序列”。如果有多个满足要求的答案，只需要找出任意一个可行解。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 110;
int path[maxn], N;
bool dfs(int u, int depth) {if (u > depth) return false;if (path[u - 1] == N) return true;bool st[maxn] = { 0 };for (int i = u - 1; i >= 0; i--) {for (int j = i; j >= 0; j--) {int s = path[i] + path[j];if (s > N || s <= path[u - 1] || st[s]) continue;st[s] = true;path[u] = s;if (dfs(u + 1, depth)) return true;}}return false;
}
int main() {path[0] = 1;while (scanf("%d", &N) && N) {int depth = 1;while (!dfs(1, depth)) depth++;//一定要小心这个答案输出！！ i 从 0 循环到 depth - 1 就行！for (int i = 0; i < depth; i++) printf("%d%c", path[i], i + 1 == depth ? '\\n' : ' ');}return 0;
}

双向dfs

• 和双向广搜思想很像。也是从两个方向搜索，减少搜索树的大小。

171. 送礼物

• 达达帮翰翰给女生送礼物，翰翰一共准备了 $N$ 个礼物，其中第 $i$ 个礼物的重量是 $G[i]$。达达的力气很大，他一次可以搬动重量之和不超过 $W$ 的任意多个物品。达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

• 背包问题，但是数据范围不允许用动态规划。枚举前 $N/2$ 种物品可以凑出来多少种重量，然后枚举出后 $N/2$ 种可以凑出来多少种，然后在前一半中查，后面用二分去寻找。

• 其实 O(2k+2N−k∗k)O(2^k + 2^{N-k}*k)O(2k+2N−k∗k)，$k$ 取 25 更好一些。

• 先将物品总量从大到小排序；将前 $K$ 件物品能凑出的所有重量打表排序判重；最后搜索剩下的 $N-K$ 件物品的选择方式，然后在表中二分出和不超过 $W$ 的最大值.

#include<cstdio>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
int N, K, cnt = 1, ans;
int weights[1 << 25], W, a[50];
void dfs1(int u, int w) {if (u == K) {weights[cnt++] = w;return;}dfs1(u + 1, w);if ((ll)a[u] + w <= W) (u + 1, a[u] + w);
}
void dfs2(int u, int w) {if (u >= N) {int lb = 0, ub = cnt;while (ub - lb > 1) {int mid = (lb + ub) / 2;if ((ll)w + weights[mid] <= W) lb = mid;else ub = mid;}ans = max(ans, w + weights[lb]);return;}dfs2(u + 1, w);if ((ll)a[u] + w <= W) dfs2(u + 1, w + a[u]);
}
int main() {scanf("%d%d", &W, &N);for (int i = 0; i < N; i++) {scanf("%d", &a[i]);}K = N / 2 + 2;sort(a, a + N, greater<int>());dfs1(0, 0);sort(weights, weights + cnt);cnt = unique(weights, weights + cnt) - weights;dfs2(K, 0);printf("%d\\n", ans);return 0;
}

IDA*

• 这个是和迭代加深搜索配合着用的。需要一个预估函数 <= 真实值

180. 排书

• 给定 $n$ 本书，编号为 $1$ ~ $n$。在初始状态下，书是任意排列的。在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。我们的目标状态是把书按照 $1$ ~ $n$ 的顺序依次排列。求最少需要多少次操作。

• 每操作一次，可以改变三个后继。用 tot 记录错误的后继数量，那么就得到了一个预估函数 $\lceil tot/3\rceil$，这就是真实值的一个下界。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 15;
int N, q[maxn], w[5][maxn];
//预估函数
int f() {int tot = 0;for (int i = 1; i < N; i++) {if (q[i] - q[i - 1] != 1) tot++;}return (tot + 2) / 3;
}
bool dfs(int depth, int max_depth) {if (depth + f() > max_depth) return false;if (f() == 0) return true;for (int len = 1; len <= N; len++) {for (int l = 0; l + len - 1 < N; l++) {int r = l + len - 1;for (int k = r + 1; k < N; k++) {int y = l;memcpy(w[depth], q, sizeof q);for (int x = r + 1; x <= k; x++, y++) q[y] = w[depth][x];for (int x = l; x <= r; x++, y++) q[y] = w[depth][x];if (dfs(depth + 1, max_depth)) return true;;memcpy(q, w[depth], sizeof q);}}}return false;
}
int main() {int T;scanf("%d", &T);while (T--) {scanf("%d", &N);for (int i = 0; i < N; i++) {scanf("%d", &q[i]);}int depth = 0;while (depth < 5 && !dfs(0, depth)) depth++;if (depth >= 5) printf("5 or more\\n");else printf("%d\\n", depth);}return 0;
}