Toggle navigation
linghang
F.A.Qs
Web Board
ProblemSet
Source/Category
Status
Ranklist
Contest
[
ProblemSet
Status
Ranklist
OI Ranklist
Statistics
]
Login
Problem C: N 皇后问题(queen.cpp)
Problem C: N 皇后问题(queen.cpp)
Time Limit:
1
Sec
Memory Limit:
128 MB
Submit:
704
Solved:
291
[
Submit
] [
Status
] [
Web Board
] [Creator:
]
Description
在 N*N 的棋盘上放置 N 个皇后(n<=10)而彼此不受攻击(即在棋盘的任一行,任一列和任一对角线上不能放置 2 个皇后),编程求解所有的摆放方法。
Input
输入:n
Output
每行输出一种方案,每种方案顺序输出皇后所在的列号,各个数之间有空格隔开。若无方案,则输出no solute!
Sample Input
Copy
4
Sample Output
Copy
2 4 1 3 3 1 4 2
HINT
样例2 4 1 3解释:
第一行站在第2列
第二行站在第4列
第三行站在第1列
第四行站在第3列
***************
以下为八皇后的框架:
void dfs( int i )
{ //搜索第i行,准备在第i行摆放皇后
for (int j=1; j<=8; j++){ //搜索第i行的8列
if (a[ i+j ]==0 && b[ i-j+7 ]==0 && c[ j ]==0){
//把该位置的和值差值及列(即两条对角线和列),做上不能再放的标志
//思考为什么要加上7
//第i行放在第j列
//进入下一行
//回到该行后,我们先解除不能放的标志,然后接着去试下一列
}
}
}