n皇后（dfs）

Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量。

Output

共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input

1 8 5 0

Sample Output

1 92 10

对于某些题目需要打表，否则超时。

解一：

a[i]表示第i行皇后所在列数。保证了不同行、不同列。

#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int n,ans,a[10]; bool check() { for(int i=1; i<=n; ++i) { for(int j=i+1; j<=n; ++j) { if(j-i==abs(a[j]-a[i])) return 0; } } } int main() { while(scanf("%d",&n)!=EOF) { int ans=0; if(n==0) break; for(int i=1; i<=n; ++i) a[i]=i; do { if(check()) ans++; } while(next_permutation(a+1,a+1+n)); cout << ans << '\n'; } return 0; }

解二：（打了个表）

#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=5e6+30; bool vis[50][50]; int n,ans[20]; bool check(int x,int y) { for(int i=1;i<x;i++) if(vis[i][y]) return 0; for(int i=1;i<y;i++) if(vis[x][i]) return 0; int xx=x-1; int yy=y-1; while(xx&&yy) { if(vis[xx][yy]) return 0; xx--; yy--; } xx=x-1; yy=y+1; while(xx&&yy<=n) { if(vis[xx][yy]) return 0; xx--; yy++; } return 1; } void dfs(int tmp) { if(tmp==n+1) { ans[n]++; return ; } for(int i=1;i<=n;i++) { if(check(tmp,i)) { vis[tmp][i]=1; dfs(tmp+1); vis[tmp][i]=0; } } } int main() { for(n=1;n<=10;n++) { memset(vis,0,sizeof(vis)); ans[n]=0; dfs(1); } while(scanf("%d",&n)!=EOF&&n) cout<<ans[n]<<'\n'; return 0; }