Acwing 3472. 八皇后

 题目如下：

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。

如何将 88 个皇后放在棋盘上（有 8×8 个方格），使它们谁也不能被吃掉！

这就是著名的八皇后问题。

对于某个满足要求的 88 皇后的摆放方法，定义一个皇后串 a 与之对应，即 a=b1b2…b8，其中 bi 为相应摆法中第 i 行皇后所处的列数。

已经知道 88 皇后问题一共有 9292 组解（即 9292 个不同的皇后串）。

给出一个数 b，要求输出第 b 个串。

串的比较是这样的：皇后串 x 置于皇后串 y 之前，当且仅当将 x 视为整数时比 y 小。

输入格式

第一行包含整数 n，表示共有 n 组测试数据。

每组测试数据占 11 行，包括一个正整数 b。

输出格式

输出有 n 行，每行输出对应一个输入。

输出应是一个正整数，是对应于 b 的皇后串。

数据范围

1≤b≤92

输入样例：

2
1
92

输出样例：

15863724
84136275

#include <bits/stdc++.h>
using namespace std;int m[8][8];
vector<int> res;void dfs(int u) {if(u == 8) {int num = 0;for(int i = 0; i < 8; i++) {for(int j = 0; j < 8; j++) {if(m[i][j] != 0)num = num * 10 + j + 1;}}res.push_back(num);return;}for(int i = 0; i < 8; i++) {bool issure = true;for (int j = 0; j < 8; j++) {if (m[j][i] == 1 || (i + j - u >= 0 && m[j][i + j - u] == 1) || (i - j + u < 8 && m[j][u - j + i] == 1)) {issure = false;break;}}if(issure) {m[u][i] = 1;dfs(u + 1);m[u][i] = 0;}}}int main() {int T = 0;cin >> T;dfs(0);sort(res.begin(), res.end());while(T--) {int b = 0;cin >> b;cout << res[b - 1] << endl;}return 0;
}