[HDU 2553]--N皇后问题(回溯)/N皇后问题的分析

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2553

N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description
在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。
 
Input
共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。
 
 
Output
共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。
 
Sample Input
1
8
5
 
Sample Output
1
92
10
 
Author
cgf
 
Source
 
Recommend
lcy   |   We have carefully selected several similar
problems for you:  1016 1312 1241 1010 2614 
 
 
N皇后问题可以说是一个经典的回溯问题,看看下面的动画对皇后问题的求解有了一个大致的想法;
[HDU 2553]--N皇后问题(回溯)/N皇后问题的分析
 
这里采用逐行放置的办法,那么就可以不用考虑皇后的横向攻击问题,只需要检查是否纵向和斜向攻击即可。
斜向判断条件"cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]",原理用一下两个表来说明
格子(x,y)的y-x标识了主对角线
 
 
0 1 2 3 4 5 6 7
-1 0 1 2 3 4 5 6
-2 -1 0 1 2 3 4 5
-3 -2 -1 0 1 2 3 4
-4 -3 -2 -1 0 1 2 3
-5 -4 -3 -2 -1 0 1 2
-6 -5 -4 -3 -2 -1 0 1
-7 -6 -5 -4 -3 -2 -1 0
 
 
 
 
 
 
 
 
 0  1  2  3  4 5 6 7
 1  2  3  4  5 6 7 8
 2  3  4  5  6 7 8 9
 3  4  5  6 7  8 9 10
 4  5  6  7  8  9 10 11
 5  6  7  8  9 10 11 12
 6  7  8  9 10 11 12 13
 7  8  9 10 11 12 13 14
格子(x,y)的x+y标识了副对角线
 
 
 
 
 
 
 
 
然后有一点特别坑的就是,这里虽然N<=10,但是是多组输入,刚开始一直超时,我习惯性的用cin输入,以为是这里的问题,
改了还是超时,各种改各种超时,最后想到也许输入100组N<=10,有重复的N,如果把每个值存贮了就不用算第二次了,改了下
总算过了。Orz~~~
 
代码如下:
 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, vis[], cnt, ans[];
void Search(int cur){
if (cur == n) cnt++;
else for (int i = ; i < n; i++){
int flag = ;
vis[cur] = i;
for (int j = ; j < cur; j++){
if (vis[cur] == vis[j] || cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]){
flag = ;
break;
}
}
if (flag) Search(cur + );
}
}
int main(){
memset(ans, -, sizeof(ans));
while (~scanf("%d", &n), n){
//while (cin >> n, n){
cnt = ;
if (ans[n] != -){
printf("%d\n", ans[n]);
continue;
}
Search();
printf("%d\n", cnt);
ans[n] = cnt;
//cout << cnt << endl;
}
return ;
}

如果要输出排列情况,代码如下:

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, vis[], cnt,T=, ans[];
void Show(){
for (int i = ; i < n; i++){
for (int j = ; j < n; j++){
if (j) cout << ' ';
if (j == vis[i]) cout << char();
else
cout << '.';
}
cout << endl;
}
}
void Search(int cur){
if (cur == n){
cout << "Case:" << T++ << endl;
Show();
cnt++;
}
else for (int i = ; i < n; i++){
int flag = ;
vis[cur] = i;
for (int j = ; j < cur; j++){
if (vis[cur] == vis[j] || cur - vis[cur] == j - vis[j] || cur + vis[cur] == j + vis[j]){
flag = ;
break;
}
}
if (flag) Search(cur + );
}
}
int main(){
memset(ans, -, sizeof(ans));
while (cout<<"请输入皇后数:",cin >> n, n){
T = ;
cnt = ;
Search();
cout << "总排列方式:"<<cnt << endl;
}
return ;
}
上一篇:Linux运维之道(大量经典案例、问题分析,运维案头书,红帽推荐)


下一篇:Struts2(五):ActionSupport