基础知识

核心原理：一条路走到黑

示意图：其含义表示，在这个图中顶层是第0层，也就是后面dfs的入口，一般从dfs(0)开始操作。

模版：

#include <iostream>using namespace std;/*** DFS* 给定一个整数 n，将数字 1∼n* 排成一排，将会有很多种排列方法。* 现在，请你按照字典序将所有的排列方法输出。*/const int N = 10;
int n;
int path[N];    // 路径
bool st[N];     // 元素是否访问过void dfs(int u){// 当前记录的数字个数到达n层 可以输出一种情况了if (u == n){for (int i = 0; i < n; i++){printf("%d ", path[i]);}printf("\n");}//还可以继续dfs搜索 这里的i是放的数值 从1~n嘛for (int i = 1; i <= n; i ++){// 如果当前层没有被使用过if(!st[i]){path[u] = i;     //假设当前层放数值i进行尝试st[i] = true;    //标记访问过了dfs(u + 1);      //继续下一层// 一定要恢复现场st[i] = false;}}
}int main(){cin >> n;dfs(0);  //从顶层也就是第0层开始return 0;
}

典型例题

例1：n皇后问题

非常经典的问题，指将n个皇后放在n * n的国际象棋棋盘上，任意两个皇后不能处于同一行、同一列或同一斜线上。

我们的策略是一行一行的试，比如在第一行的时候，我们尝试把第一个皇后放在所有列上的后续情况全部尝试一边，注意在这个过程中如果遇到不符合题目的情况需要及时剪枝。

在判断的过程中，除了行和列不能重复，最关键的是对角线的处理，这个分为对角线和反对角线，参考y = ax + b这条直线的截距进行理解

最终代码：

#include <iostream>using namespace std;const int N = 20;
int n;
char g[N][N];   // 记录方案 使用字符串记录 
bool col[N], dg[N], udg[N];     // 标记  当前列是否放置过 当前对角线是否放置 当前反对角线是否放置 行不用考虑 因为dfs逐层下搜void dfs(int u){// 当前记录的数字个数到达n层 可以输出一种情况了if (u == n){for (int i = 0; i < n; i++){puts(g[i]);}printf("\n");}//还可以继续dfs搜索 这里的i是放的列值 从0~n-1嘛   对角线怎么设置的for (int i = 0; i < n; i ++){// 如果当前列 对角线 反对角线没有被使用过if(!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q';     //假设当前行u 的第i列可以放置col[i] = dg[u + i] = udg[n - u + i] = true;    //标记访问过了  注意对角线dfs(u + 1);      //继续下一层// 一定要恢复现场col[i] = dg[u + i] = udg[n - u + i] = false;g[u][i] = '.';}}
}int main(){cin >> n;for (int i = 0; i < n; i ++){for (int j = 0; j < n; j++){g[i][j] = '.';}}dfs(0);  //从顶层也就是第0层开始return 0;
}

方法2：每一个格子进行枚举

这个的思想就是每个格子都尝试一下能不能放皇后，遍历所有情况。

#include <iostream>using namespace std;const int N = 20;
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];// x 是行  y是列 s是当前摆下的皇后的个数
void dfs(int x, int y, int s){if (y == n){// 越界后 直接切换到下一行的第一个位置x ++;y = 0;}if (x == n){if (s == n){//完全摆完了 可以进行输出for (int i = 0; i < n; i ++){puts(g[i]);}printf("\n");}return;   //这里一定要记得return 因为还没完全结束所有情况}//正常走到这个格子了 下面就两种操作 一个是放皇后 一个是不放// 尝试不放 直接下一个// dfs(x, y ++, s);  这里太吓人了  一定不能用这种自增 要不然就死循环了dfs(x, y + 1, s);// 尝试放皇后 需要看能否放if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]){g[x][y] = 'Q';row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;// 下一个// dfs(x, y ++, s ++);dfs(x, y + 1, s + 1);// 恢复现场row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;g[x][y] = '.';}}int main(){cin >> n;for (int i = 0; i < n; i ++){for (int j = 0; j < n; j ++){g[i][j] = '.';}}// 0行 0列 也就是第一个格子  当前放置的皇后数为0；dfs(0, 0, 0);return 0;
}

例2：拍照

题面：小 A、小 B、小 C、小 D、小 E 五个人 拍照，我们会输入一些前提条件，当id为1的时候，表示后面跟的两个字母对应的人需要相邻，id为2的时候，后面跟的两个字母对应的人需要相隔，最终输出多少种拍照方案

思考转换：

转换为dfs进行求解，就是把这5个人进行排序，比如先尝试把A放在第一个位置，后面尝试所有站位可能，在这个过程中，我们需要借助限制选项，比如相邻还是相隔，可以实现提前剪枝，如果当前的站位方案不符合限制条件，也就是过不了我们的check函数，就直接剪掉。

最终代码：

#include <iostream>using namespace std;/*** 小 A、小 B、小 C、小 D、小 E 五个人 * 转换成dfs 就相当于5个人排位置  只不过添加了一些限制条件 进行剪枝*/// 整个结构体
struct limit{int id;char x, y;
}a[100];int res;
bool vis[105];
int path[1005];
int m;bool check(){// 遍历检查限制for (int i = 0; i < m; i ++){int id = a[i].id, x = a[i].x - 'A' + 1, y = a[i].y - 'A' + 1;// 这里一定要分清 位置和人物标号的关系int posx = 0, posy = 0;for (int i = 1; i <= 5; i ++){if (path[i] == x){posx = i;}if (path[i] == y){posy = i;}}// 这是要相邻if (id == 1){// 思考 path[x] 代表的含义 我们应该找出第x个人所在的位置if (abs(posx - posy) > 1){return false;  //没有相邻}}// 必须不能相邻if (id == 2){if (abs(posx - posy) == 1){return false;  //没有相邻}}}return true;
}
void dfs(int x){if (x == 5){if (check()){res ++;}   return;   // 当前结束，方案可能有多种，直接回退测试下一个方案}// 尝试着5个人都放在当前位置for (int i = 1; i <= 5; i ++){if (!vis[i]){path[x] = i;   // 第x这个位置 放在第i个人vis[i] = true;dfs(x + 1);vis[i] = false;}}}int main(){cin >> m;for (int i = 0; i < m; i ++){cin >> a[i].id >> a[i].x >> a[i].y;}dfs(0);  // 从顶层 也就是第0层开始cout << res;return 0;
}

例3：理发

题面：

思考转换：这个转换的思路在于选定一个标准进行dfs，因为先进行洗头，所有人都要先洗头，我们就把洗头的顺序作为dfs执行的标准，尝试所有顾客开始洗头的顺序，洗头确定之后，可以覆盖所有组合情况，后面剪头就只能按照实际情况进行，不断更新记录用时最短的方案。

最终代码：

#include <iostream>
#include <queue>using namespace std;const int N = 11;
int a[N], b[N];  //洗发和剪发
int n;
int res = 1e9;   
int path[1005];
bool vis[105];// 首先可以明白 我们dfs的对象是什么 是洗头的顺序安排剩下的剪头只能被迫安排
void dfs(int x){if (x == n){int y1 = 0, y2 = 0;   // 洗头顺序固定的情况下 寻找最短总时间priority_queue<int> q;for (int i = 0; i < n; i ++){int peo = path[i];  //第i个人y1 += a[peo];         // 第i个人洗发// 剪发时间 进入优先队列q.push(b[peo]);y2 = max(y2, y1);  // y2是担心之前还有人没剪完头int w = q.top();    //剪发 读队中头 自动排序 最大的  读完pop出队q.pop();        y2 += w;   }res = min(y2, res);return;}for (int i = 0; i < n; i ++){if (!vis[i]){vis[i] = true;path[x] = i;   // 谁都有机会放在第一个 dfs(x + 1);vis[i] = false;}}
}int main(){int t;cin >> t;while (t --){cin >> n;res = 1e9;for (int i = 0; i < n; i ++){cin >> a[i] >> b[i];}dfs(0);cout << res << endl;}return 0;
}