题目描述
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
输入样例
1
8
5
0
输出样例
1
92
10
AC代码
#include <iostream>
#include<cstring>
using namespace std;
const int MAX_NUM = 11;
int cnt = 0 ,board[MAX_NUM] , ans[MAX_NUM];
void output_ans(int n){
cout << ans[n] << endl;
}
// 判断第i行的第k列是否可以放置
bool judge_ok(int find_row_index , int find_col_index){
for(int cur_row = 1 ; cur_row < find_row_index ; cur_row ++){
if(board[cur_row] == find_col_index || abs(cur_row - find_row_index ) == abs(board[cur_row] - find_col_index) ){
return false;
}
}
return true;
}
void place_queen(int row_index , int n){
if(row_index > n){
//cnt ++ ;
ans[n] ++ ;
return ;
}
// 判断当前行的每一列
for(int cur_col = 1 ; cur_col <= n ; cur_col ++){
if(judge_ok(row_index , cur_col )){
board[row_index] = cur_col;
place_queen(row_index + 1 , n);
}
}
}
int main()
{
int n ;
while(cin >> n && n != 0){
memset(board , 0 , sizeof(board));
if(ans[n] != 0){
output_ans(n);
continue;
}
place_queen(1 , n);
output_ans(n);
}
return 0;
}
思路描述
题目大意
输入一个正整数（<=10），可设置最大数字MAX_NUM = 10
输出总共有多少种方案，需要进行枚举，设置全局变量数组ans
代码解释
首先对循环输入，结束条件为n = 0
while(cin >> n && n != 0)
这是一个很好的多组输入的模板方法
若题目中出现出现多组输入，而且没有结束的输入条件就可以直接使用
while(cin >> n){
然后进行判断是否当前的n是否已经计算过，这点一定要注意！！！
if(ans[n] != 0)
我第一次提交代码就是因为没有对这个进行处理，然后导致超时了
当时我想的是，n就1-10，就没有去存了
而且自己测试我直接输入10也很快就给出答案，就直接提交了
结果超时了！！
因为还需要考虑到如果测试用例中，全部都是10，每次都计算一遍，时间就会显得很长！！！
执行最主要的函数，函数大致功能就是循环递归放置皇后，并在行超过n时，cnt累加
传入参数
- 行下标——
row_index - 最大列下标——
n
意为，从当前的行下标判断在每一列上放置皇后
大致执行逻辑
若当前递归的行下标row_index是否大于放置个数n
-
大于
- ans[当前下标] ++
- 返回函数
-
小于或等于
- 放置皇后
放置皇后的具体逻辑
对当前行row_index每一列放置皇后
-
判断当前行
row_index和当前列cur_col是否可放置——judgeOk函数-
可放置
-
将当前的列下标 赋值给 当前棋盘上的行下标
board[row_index] = cur_col -
递归自身——行数+1
-
-
judgeOk函数逻辑
判断该行该列是否可以放置皇后
传入参数
find_row_index——查询的行下标find_col_index——查询的列下标
从行数1——当前查询的行下标find_row_index循环
-
判断
-
棋盘的当前行是否等于当前列下标——不能在同一行
因为在刚开始时，改函数返回的是true
则在放置皇后函数中，将会放置皇后
board[row_index] = cur_col -
当前行下标 - 查询的行下标与棋盘对应结果 - 查询的列下标的绝对值进行比较——45度判断-
是
- 返回false
-
-
最后返回true
