百练 OJ 2754 八皇后问题

//转载请写上本帖链接:http://www.wutianqi.com/?p=169
//及【C++奋斗乐园/ACM乐园】

/****************************************
ID: 百练 OJ 2754 八皇后问题
题目地址: http://poj.grids.cn/problem/2754/
My Name: Tanky_Woo
My Website: C++奋斗乐园|C++学习|算法学习|ACM/ICPC学习
Website Link: http://www.cpply.com/

My BBS: C++奋斗乐园|C++论坛|算法论坛|ACM/ICPC论坛
BBS Link:http://www.cppleyuan.com/

My Blog:www.wutianqi.com
豆瓣小组:http://www.douban.com/group/cppleyuan/
QQ:17611904
QQ群:C++奋斗乐园①群:19333724(满) ②群:23840480 (满)
③群:17314377 ④群:23829384
*****************************************/

//方法一:
此方法不用8*8的仿真棋盘来模拟控制区域,而只用一个有8个元素的数组记录已经摆放的棋子摆在什么位置,当要放置一个新的棋子时,只需要判断它与已经放置的棋子之间是否冲突就可以了。
//内存: 1848kb 时间: 0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 #include <iostream>
using namespace std;
int ans[92][8], hang[8], num = 0;
 
 
int queen(int i)
{
	int j, k;
	if(i == 8)   //一组新的解产生
	{
		for(j = 0; j < 8; j++)
			ans[num][j] = hang[j] + 1;
		num++;
		//memset(hang, 0, sizeof(hang));  这个地方还不能置0
	}
	if(num == 93)
		return 0;
	for(j = 0; j < 8; j++)   //将当前皇后i逐一尝试放在不同的列
	{
		for(k = 0; k < i; k++)  //逐一判定i与前面的皇后是否冲突
			if(hang[k] == j || (k-i) == (hang[k]-j) || (i-k)==(hang[k]-j))
				break;
		if(k == i)
		{
			hang[i] = j;
			queen(i+1);
			hang[i] = 0;  //加了这步后由16ms变成0ms
		}
	}
}
 
int main()
{
	num = 0;
	queen(0);
	int n;
	scanf("%d", &n);
	for(int i =