直观的判断,在check函数里面
#include <iostream>
using namespace std;
const int N = 10;
char g[N][N];
int n;
bool check(int x, int y)
{
for(int j = 0; j < n; j ++ ) if(j != y && g[x][j] == 'Q') return false; // (x,y)水平方向有皇后
for(int i = 0; i < n; i ++ ) if(i != x && g[i][y] == 'Q') return false; // (x,y)竖直方向有皇后
int cnt = 1;
while(x - cnt >= 0 && y - cnt >= 0){
if(g[x - cnt][y - cnt] == 'Q') return false; // (x,y)左上方有皇后
cnt ++ ;
}
cnt = 1;
while(x - cnt >= 0 && y + cnt < n){
if(g[x - cnt][y + cnt] == 'Q') return false; // (x,y)右上方有皇后
cnt ++ ;
}
cnt = 1;
while(x + cnt < n && y - cnt >= 0){
if(g[x + cnt][y - cnt] == 'Q') return false; // (x,y)左下方有皇后
cnt ++ ;
}
cnt = 1;
while(x + cnt < n && y + cnt < n){
if(g[x + cnt][y + cnt] == 'Q') return false; // (x,y)右下方有皇后
cnt ++ ;
}
return true;
}
void dfs(int x)
{
if(x == n){
for(int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
return;
}
for(int i = 0; i < n; i ++ ){
g[x][i] = 'Q'; // 尝试在(x,i)处放一个皇后
if(check(x, i)) dfs(x + 1); // 如果能放下则继续
g[x][i] = '.'; // 不能放下则恢复现场
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
y总的用数组保存所有皇后的状态可以O(1)求冲突,定义顺序从第一行枚举到最后一行 那么行一定不会冲突 定义col[1-N]数组 初始值全为0 哪一列有皇后就把对应下标的col[j]设置为1 两条对角线分别用另外2个数组存一下 代码即好写效率还高 而且N皇后问题数据范围不会很大 空间复杂度可以忽略不计。