AcWing 843. n-皇后问题
原题链接
中等
#include <iostream>
using namespace std;
const int N = 10;
int n;
int st[N][N];
bool check(int i, int j)
{
for(int k = 1; k <= n; k ++)
{
// 检查同一行
if (st[k][j] && k != i)
return false;
// 检查同一列
if (st[i][k] && k != j)
return false;
// 检查正对角线
if (i - k >= 1 && j - k >= 1 && st[i - k][j - k])
return false;
if (i + k <= n && j + k <= n && st[i + k][j + k])
return false;
// 检查反对角线
if (i - k >= 1 && j + k <= n && st[i - k][j + k])
return false;
if (i + k <= n && j - k >= 1 && st[i + k][j - k])
return false;
}
return true;
}
void dfs(int u)
{
// 搜索到n+1行说明搜索完了
if (u == n + 1)
{
for(int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
{
if (st[i][j])
printf("Q");
else
printf(".");
}
printf("\n");
}
printf("\n");
}
// 搜索第u行的每一列
for (int i = 1; i <= n; i ++)
{
if (check(u, i))
{
st[u][i] = true;
// 搜索下一行
dfs(u + 1);
// 回溯
st[u][i] = false;
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
%%%