AcWing 843. n-皇后问题
原题链接
中等
作者:
此间
,
2021-04-17 18:36:57
,
所有人可见
,
阅读 313
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 25;
int n;
char q[N][N];
bool row[N],col[N], dg[N], udg[N];//所在的行和对角线
void dfs(int x,int y,int s)
{
if (s > n)return;//如果皇后数量大于n的话就回溯
if (y == n)//如果y移动到最右边,那么就进入下一行
{
y = 0;
x++;
}
if (x == n)
{
if (s == n)
{
for (int i = 0; i < n; i++)puts(q[i]);
puts("");
}
return;
}
q[x][y] = '.';
dfs(x, y + 1, s);//这个位置不放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
q[x][y] = 'Q';
dfs(x, y + 1, s + 1);
q[x][y] = '.';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
}
}
int main() {
ios::sync_with_stdio;
cin >> n;
dfs(0,0,0);
return 0;
}