「codecomb2094」还是N皇后

2014年10月15日3,0110

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一位一位取出即可

 

avatar
  Subscribe  
提醒