题目
皇后问题是指将 个皇后放在 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 ，请你输出所有的满足条件的棋子摆法。
输入格式
共一行，包含整数 。
输出格式
每个解决方案占 行，每行输出一个长度为 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。
数据范围
输入样例：
4
输出样例：
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <iostream>
#include <vector>
#define N 15
using namespace std;
int n;
void dfs(int u, vector<int> &dx, bool col[], bool dg[], bool udg[])
{
if (u == n)
{
if (dx.size() == n)
{
for (int i = 0; i < n; ++ i)
{
for (int j = 0; j < n; ++ j)
if (j == dx[i]) printf("Q");
else printf(".");
puts("");
}
puts("");
}
return;
}
++ u;
for (int i = 0; i < n; ++ i)
{
if (!col[i] && !dg[i - u + n + 1] && !udg[i + u])
{
col[i] = dg[i - u + n + 1] = udg[i + u] = true;
dx.push_back(i);
dfs(u, dx, col, dg, udg);
dx.pop_back();
col[i] = dg[i - u + n + 1] = udg[i + u] = false;
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++ i)
{
bool col[N] = {false}, dg[2 * N] = {false}, udg[2 * N] = {false};
vector<int> dx;
col[i] = dg[i - 1 + n + 1] = udg[i + 1] = true;
dx.push_back(i);
dfs(1, dx, col, dg, udg);
}
return 0;
}
|
