题目一：排序数字
842. 排列数字 - AcWing题库
分析
考虑dfs，其实stl——next_permutation也可以
路径存储开一个数组，不能重复搜索，加一个标记数组
代码
#include<bits/stdc++.h>
using namespace std;int path[10];
int n;
bool vis[10];void dfs(int u) {if(u == n) { // 存完0-n-1，之后进入下一层输出层for(int i = 0; i < n; i ++) cout << path[i] << " ";puts("");return ;}for(int i = 1; i <= n; i ++) {if(!vis[i]) {vis[i] = true;path[u] = i;dfs(u+1);vis[i] = false;}}
}int main() {cin >> n;dfs(0);return 0;
}题目二：n-皇后问题
843. n-皇后问题 - AcWing题库
分析
考虑dfs遍历每一列
用二维数组存图
用col标记一列，用dg 数组标记一条对角线，用udg标记一条反对角线
对角线表示：
截距 y = x +k, k = y-x. 即k = u-i (但是u-i可能为负数，数组越界 u-i + n)
反正对应一个空间标记一条线就行
y = -x + k, k = y+x 即 k = u+i
代码
#include<bits/stdc++.h>
using namespace std;const int N = 11;
int n;
char a[N][N];
int col[N], dg[N], udg[N];void dfs(int u) {if(u == n) {for(int i = 0; i < n; i ++) {for(int j = 1; j <= n; j ++) {cout << a[i][j];}puts("");}puts("");return ;}for(int i = 1; i <= n; i ++) {if(!col[i] && !dg[i+u] && !udg[u-i+n]) {char t = a[u][i];a[u][i] = 'Q';col[i] = dg[i+u] = udg[u-i+n] = 1;dfs(u+1);col[i] = dg[i+u] = udg[u-i+n] = 0;a[u][i] = t;}}
}int main() {cin >> n;for(int i = 0; i < n; i ++) for(int j = 1; j <= n; j ++) a[i][j] = '.';dfs(0);return 0;
}
