AcWing 843. n-皇后问题
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
char g[15][15];
int n;
bool cu[15] , ro[15] , dg[15] , udg[15];
void dfs(int r , int count)
{
if(r == n + 1) return;
if(count == n)
{
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n; j++) cout << g[i][j];
cout << endl;
}
cout << endl;
return;
}
for(int i = 0 ; i < n ; i++)
{
if(!cu[i] && !dg[i + r] && !udg[i - r + n])
{
g[r][i] = 'Q';
cu[i] = dg[i + r] = udg[i - r + n] = true;
dfs(r + 1 , count + 1);
g[r][i] = '.';
cu[i] = dg[i + r] = udg[i - r + n] = false;
}
}
}
int main()
{
//init
cin >> n;
for(int i = 0; i <= n; i++)
{
for(int j = 0 ; j <= n; j++) g[i][j] = '.';
}
dfs(0 , 0);
return 0;
}