ACM-遞歸之n皇後——hdu2553

N皇後問題

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

Total Submission(s): 6950 Accepted Submission(s): 3150

Problem Description

在N*N的方格棋盤放置了N個皇後，使得它們不互相攻擊（即任意2個皇後不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上。

你的任務是，對于給定的N，求出有多少種合法的放置方法。

Input

共有若幹行，每行一個正整數N≤10，表示棋盤和皇後的數量；如果N=0，表示結束。

Output

共有若幹行，每行一個正整數，表示對應輸入行的皇後的不同放置數量。

Sample Input

1

8

5

Sample Output

1

92

10

這道題，不容易啊，一道遞歸題目，

它的方法就是，你遞歸傳的是行号，建立一個數組，

數組下标表示第幾行，數組内容表示皇後在第幾列，

至于會不會在同一行或者同一列或者45°角問題，

同一行：每次遞歸 行号+1，是以不可能在同一行，

同一列：這就需要循環了，數組存了第幾列，可以判斷，一個循環足夠

45°角：這個也是要循環，仔細研究發現  兩個皇後  橫坐标差的絕對值若等于縱坐标差的絕對值，那肯定不能同時存在

遞歸什麼時候停止呢？

傳的是行号，當行号大于n的時候，

比如要求3x3時候，若行号大于3，則停止，++total,

這就是解題方案，很簡單吧，對了，這道題，不可能，你輸入n然後現搜尋，必須要打表

就是提前算出來，因為N小于等于10，用一個數組存答案，while輸入一個N,輸出相應數組下标的值

好了，這樣AC即将來臨！

O(∩_∩)O哈！

代碼：

#include <iostream>
#include <cmath>
using namespace std;
// sl存的是種數，即答案。  row存的是，下标行的列數，
// 比如 row[1]=1  代表第一行第一列有一個皇後
int sl[11],row[11];
int total,m;


void search(int hang)
{
	if(hang>m)
	{
		++total;
		return;
	}

	int x=hang,i,y;
	for(y=1;y<=m;++y)
	{
		for(i=1;i<x;++i)
			if(row[i]==y)
				break;
		if(i<x)	continue;

		for(i=1;i<x;++i)
			if(abs(row[i]-y)==abs(x-i))
				break;
		if(i<x)	continue;

		row[x]=y;
		search(hang+1);
	}
}

int find()
{
	total=0;
	search(1);
	return total;
}

int main()
{
	// 要打表喲，否則TLE啦
	for(m=1;m<=10;++m)
		sl[m]=find();	

	int n;
	while(cin>>n && n!=0)
	{
		cout<<sl[n]<<endl;
	}

	return 0;
}