对角线的写法
//朝着一个方向的对角线,斜率相同,但是截距不同,并且截距唯一。
//所以可以用截距作为下标来代表一条唯一的对角线。
//对于斜率位 1 的对角线:
//y = x + b -> b = y - x 因为y - x可能为负数,+n偏移量。
//因为对角线数组为2(n + 1),所以不会越界。
//对于斜率为-1的对角线:
//y = -x + b -> b = y + x, x + y <= 2n
#include<bits/stdc++.h>
using namespace std;
const int N = 13;
int n;//p[i]表示第i行的皇后放在了第p[i]列
char p[N][N];
bool dg[2*N],udg[2*N],col[N];//标记某个位置下,其对角线、反对角线、列的使用状态
void DFS(int u) //调用一次DFS()代表对某行中所有的列进行判断
{
if(u==n+1) //u==n+1的原因,当u==n即进行n行的操作,但由于此时n行的操作还没有
{ //进行完,所以要到n+1行才能判断n行的状态
for(int i = 1;i<=n;i++){ //覆盖打印 //一个答案的找出,取决于其是否进行了最终打印
for(int j = 1;j<=n;j++)
cout << p[i][j];
cout << endl; //每行的所有列打印完后,要换行一次
}
cout << endl;
return;
}
for(int i = 1;i<=n;i++)
{
if(!col[i]&&!dg[u+i]&&!udg[u-i+n])
{
p[u][i] = 'Q';
dg[u+i]=udg[u-i+n]=col[i]=true; //该点对应的对角线、反对角线、列都已被
DFS(u+1); //污染,三者对应的点不可再被使用
dg[u+i]=udg[u-i+n]=col[i]=false; //需要在其他环境下,在寻找符合答案的可能
p[u][i] = '.'; //所以要进行还原
}
}
}
int main()
{
cin >> n;
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
p[i][j] = '.';
DFS(1); //以行进行深度搜索
return 0;
}