「codecomb2094」还是N皇后
Description
正如题目所说，这题是著名的N皇后问题。
Input Format
第一行有一个N。接下来有N行N列描述一个棋盘，“*”表示可放“.”表示不可放。
Output Format
输出方案总数。
Sample Input
4
**.*
****
****
****
Sample Output
1
Data Limit
对于30%的数据，N≤10;
对于100%的数据，N≤14；
题解
裸的dfs不足以ac
我发现n皇后可以用位运算加速
参见http://blog.csdn.net/xadillax/article/details/6512318
然后就能水过了。。。
说白了就是每一层原来要for n个位置
用位运算就能得出要for 哪些位置
然后用lowbit一位一位取出即可
|
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 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans,ed; char a[15][15]; int f[15]; void dfs(int k,int x,int l,int r) { if(x!=ed) { int tmp=ed^(~(x|l|r|f[k])); while(tmp!=0) { int t=tmp&(-tmp); tmp-=t; dfs(k+1,x+t,(l+t)<<1,(r+t)>>1); } } else ans++; } int main() { n=read();ed=(1<<n)-1; for(int i=1;i<=n;i++) scanf("%s",a[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]=='.')f[i]+=1<<(j-1); dfs(1,0,0,0); printf("%d",ans); return 0; } |
Subscribe
计数器 9856825
OI 课件=>
OI 课件=>