用C++编写八皇后问题,第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数b(1 <= b <= 92),输出有n行,每行输出对应一个输入。输出应是一个正整数,是对应于b的皇后串并给出详细代码
时间: 2024-03-10 10:43:31 浏览: 124
好的,以下是用 C++ 编写八皇后问题的代码,可处理多组测试数据并输出对应的皇后串:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 判断当前位置是否能放置皇后
bool canPlace(vector<int>& board, int row, int col) {
for (int i = 0; i < row; ++i) {
// 检查同一列是否有皇后
if (board[i] == col) {
return false;
}
// 检查对角线是否有皇后
if (abs(row - i) == abs(col - board[i])) {
return false;
}
}
return true;
}
// 回溯求解八皇后问题
void backtrack(vector<int>& board, int row, int b, int& count, vector<int>& solution) {
if (row == board.size()) { // 找到一个解
count++;
if (count == b) { // 找到第 b 个解
solution = board;
}
return;
}
for (int col = 0; col < board.size(); ++col) {
if (canPlace(board, row, col)) {
board[row] = col;
backtrack(board, row + 1, b, count, solution);
board[row] = -1; // 恢复现场
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int b;
cin >> b;
int size = 8;
vector<int> board(size, -1);
int count = 0; // 可行解的数量
vector<int> solution(size, -1); // 第 b 个解
backtrack(board, 0, b, count, solution);
for (int j = 0; j < size; ++j) {
cout << solution[j] + 1 << " "; // 输出皇后串
}
cout << endl;
}
return 0;
}
```
对于每个测试用例,我们先输入测试数据的组数 `n`,然后依次处理每组测试数据。每组测试数据包括一个正整数 `b`,表示要找到第 `b` 个可行解。我们创建一个大小为 8 的向量 `board`,初始值均为 -1,表示棋盘上每个位置都没有放置皇后。然后从第一行开始,依次尝试在每个位置放置皇后,如果能放置就递归到下一行,否则继续尝试下一个位置。当放置完最后一行时,我们就找到了一个可行解,将计数器 `count` 加 1,如果 `count` 等于 `b`,就将当前的解存储到向量 `solution` 中。最终,我们输出向量 `solution` 中的值加 1 即可得到对应的皇后串。
阅读全文