只是因为期末来了，不想断了手感又不想耽误复(预)习，所以开始重新写下基础课的题保持手感。

关于$dfs$：
① 全排列
② $n$皇后
时间复杂度：$O(n!)$

考虑到破坏现场和恢复现场两个问题：
$dfs(u)$ 表示当前已经到了第$u$层，然后遍历所有情况选择一种合法的继续往下搜。

① 全排列
题意：
给定数字$n$，输出$1-n$这$n$个数字的全排列
数据范围：$1\leq n\leq 7$
题解：
破坏现场：vis[u] = true, a[u] = i
恢复现场：vis[u] = false，删去a[u]中的数
用a[u]记录第$u$层的数
代码：
参考代码

② $n$皇后
题意：
在$n\times n$的矩阵中放$n$个皇后，并且这$n$个皇后中，两两不能在同一行，同一列，同一对角线（正反对角线都不可以），输出所有合法放置方案。
数据范围：$1\leq n\leq 9$

题解：
破坏现场：由于我们是按行枚举的，所以不会存在同一行的冲突。
考虑枚举到的当前点：$(u,v)$，所在列$v$是否被占领，所在正对角线和反对角线是否被占领。
恢复现场：将我们之前占领的列$v$，正对角线和反对角线都取消占领。

本题难点在于考虑正对角线和反对角线，可以从图像角度理解。
正对角线的图像：$y = x + b$
反对角线的图像：$y = -x + b$
所有对角线的不同点在于截距$b$的不同，故以$b$作为对角线是否被占用标记即可。
对于正对角线：$b = y - x$，为了避免负数的麻烦，设置为$y - x + n$即可
对于反对角线：$b = x + y$。

代码：
参考代码