赞
踩
题目描述
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
输入
一个整数n( 1 < = n < = 10 )
输出
每行输出对应一种方案,按字典序输出所有方案。每种方案顺序输出皇后所在的列号,相邻两数之间用空格隔开。如果一组可行方案都没有,输出“no solute!”
样例输入 Copy
4
样例输出 Copy
2 4 1 3 3 1 4 2
思路:基于全排列的思想来做。不过在生成完p数组再去判断效率太低, 可以在边生成p的时候边判断,后面在优化吧= -。
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- int p[15], hashtable[15] = {0}, n, flag1 = 0;//flag1 标记存不存在方案
- void dfs(int index) {
- if(index == n+1) {
- int flag = 1;
- for(int i = 1; i <= n; i++) {
- for(int j = i + 1; j <= n; j++) {
- if(abs(i - j) == abs(p[i] - p[j])) {
- flag = 0;
- break;
- }
- }
- if(!flag) break;
- }
- if(flag) {
- printf("%d", p[1]);
- for(int i = 2; i <= n; i++) {
- printf(" %d", p[i]);
- }
- printf("\n");
- flag1 = 1;
- }
- return;
- }
- for(int x = 1; x <= n; x++){
- if(hashtable[x] == 0){
- p[index] = x;
- hashtable[x] = 1;
- dfs(index + 1);
- hashtable[x] = 0;
- }
- }
- }
- int main(int argc, char** argv) {
- while(cin >> n) {
- dfs(1);
- if(!flag1){//如果不存在方案
- printf("no solute!\n");
- }
- }
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。