题目描述
皇后问题是指将 n
个皇后放在 n×n
的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。
现在给定整数 n,请你输出所有的满足条件的棋子摆法。
样例
输入样例:
4
输出样例:
.Q..
…Q
Q…
..Q.
..Q.
Q…
…Q
.Q..
思路一 全排列思想
、#include[HTML_REMOVED]
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
char g[N][N];
bool col[N],dg[N],ug[N];
int n;
void dfs(int u){
if(u == n){
for(int i = 0; i < n ; i ) puts(g[i]);
puts(” “);
return;
}//u表示每一行 i则表示每一列
for(int i = 0; i < n; i ){
if(!col[i] && !dg[u + i]&& !ug[n - u + i]){
g[u][i] = ‘Q’;
col[i] = dg[u + i] = ug[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = ug[n - u + i] = false;
g[u][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;
}
解法二 原始
include[HTML_REMOVED]
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
char g[N][N];
bool row[N], col[N],dg[N],ug[N];
int n;
void dfs(int x, int y, int s){
if(y == n) x ++, y = 0;
if(x == n){
if(s == n) for(int i = 0 ; i < n ;i ++) {
puts(g[i]);
puts("");
}
return;
}
dfs(x, y + 1, s);
if(!row[x] && !col[y] && !dg[x + y] && !ug[x - y + n]){
g[x][y] = ‘Q’;
row[x] = col[y] = dg[x+ y] = ug[x - y +n] = true;
dfs(x,y+1,s+1);
row[x] = col[y] = dg[x+ y] = ug[x - y +n] = false;
g[x][y] = ‘.’;
}
}
int main(){
cin>> n;
for(int i = 0; i < n; i)
for(int j = 0; j < n; j ){
g[i][j] = ‘.’;
}
dfs(0,0,0);
return 0;
}