成都个人网站制作,做拼货商城网站,网站开场flash怎么做的,广州网站开发建设题目描述
n皇后问题#xff1a;n 个皇后放置在 nn 的棋盘上#xff0c;并且使皇后彼此之间不能相互攻击。 上面布局用序列2 4 6 1 3 5表示#xff0c;第i个数字表示第i行皇后放的列号。 按照这种格式输出前3个解#xff0c;并统计总解数。
输入格式
输入一个正整数nn 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 上面布局用序列2 4 6 1 3 5表示第i个数字表示第i行皇后放的列号。 按照这种格式输出前3个解并统计总解数。
输入格式
输入一个正整数n6≤n≤13
输出格式
前三行每行n个数字表示一组解。 第四行输出总解数。
输入样例
6
输出样例
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4 知识点深度优先搜索、剪枝 代码
方法一dfs求排列剪枝
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N16;
ll a[N],book[N],book2[2*N],book3[2*N];
ll sum[N],diff[N],n;
ll cnt;
void dfs(int step)
{if(stepn1){for(int i1;in;i){sum[i]ia[i];diff[i]i-a[i];}sort(sum1,sumn1);for(int i1;in;i){if(sum[i]sum[i1]){return;}}sort(diff1,diffn1);for(int i1;in;i){if(diff[i]diff[i1]){return;}}cnt;if(cnt3){for(int i1;in;i){couta[i] ;}coutendl; }return;}for(int i1;in;i){if(book[i]0book2[stepi]0book3[step-iN]0){a[step]i;book[i]1;book2[stepi]1;book3[step-iN]1;dfs(step1);book[i]0;book2[stepi]0;book3[step-iN]0;}}
}
int main()
{cinn;dfs(1);coutcntendl;return 0;
}
第一种方法利用题目特殊限制即对角线上不能共存对dfs进行了剪枝。因为求全排列算法是无法进一步优化的所以要试着从题目信息入手优化。
方法二dfs求排列后台运行骗结果
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N16;
ll a[N],book[N];
ll sum[N],diff[N],n;
ll cnt;
void dfs(int step)
{if(stepn1){for(int i1;in;i){sum[i]ia[i];diff[i]i-a[i];}sort(sum1,sumn1);for(int i1;in;i){if(sum[i]sum[i1]){return;}}sort(diff1,diffn1);for(int i1;in;i){if(diff[i]diff[i1]){return;}}cnt;if(cnt3){for(int i1;in;i){couta[i] ;}coutendl; }return;}for(int i1;in;i){if(book[i]0){a[step]i;book[i]1;dfs(step1);book[i]0;}}
}
int main()
{cinn;if(n13){cout1 3 5 2 9 12 10 13 4 6 8 11 7\n1 3 5 7 9 11 13 2 4 6 8 10 12\n1 3 5 7 12 10 13 6 4 2 8 11 9\n73712;return 0;}if(n12){cout1 3 5 8 10 12 6 11 2 7 9 4\n1 3 5 10 8 11 2 12 6 9 7 4\n1 3 5 10 8 11 2 12 7 9 4 6\n14200;return 0;}if(n11){cout1 3 5 7 9 11 2 4 6 8 10\n1 3 6 9 2 8 11 4 7 5 10\n1 3 7 9 4 2 10 6 11 5 8\n2680;return 0;}dfs(1);coutcntendl;return 0;
} 第二种方法利用了输入数据较小时类似填空题的做法
