n皇后问题c++变形
时间: 2024-01-04 18:20:02 浏览: 87
c++ N皇后问题
以下是一个C++实现的n皇后问题的变形,使用深度优先搜索(DFS)算法:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 判断当前位置是否可以放置皇后
bool isValid(vector<int>& queens, int row, int col) {
for (int i = 0; i < row; i++) {
// 判断是否在同一列或同一斜线上
if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) {
return false;
}
}
return true;
}
// 深度优先搜索
void dfs(vector<vector<string>>& res, vector<int>& queens, int row, int n) {
if (row == n) {
// 生成棋盘
vector<string> board(n, string(n, '.'));
for (int i = 0; i < n; i++) {
board[i][queens[i]] = 'Q';
}
res.push_back(board);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(queens, row, col)) {
queens[row] = col;
dfs(res, queens, row + 1, n);
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<int> queens(n, -1);
dfs(res, queens, 0, n);
return res;
}
int main() {
int n = 4;
vector<vector<string>> res = solveNQueens(n);
// 输出结果
for (int i = 0; i < res.size(); i++) {
cout << "Solution " << i + 1 << ":" << endl;
for (int j = 0; j < n; j++) {
cout << res[i][j] << endl;
}
cout << endl;
}
return 0;
}
```
阅读全文