USACO/checker
来自"NOCOW"
目录 |
[编辑] 分析
[编辑] DFS+优化
因为要遍历整棵搜索树，所以用DFS，我们可以在搜索时加入剪枝，记录横行和两条斜线是否被攻击，每次只放在不受任意方向攻击的地方。 这个剪枝过最后一个数据需要2s，超时。(准确的说，是1.2s -Seek Final)
[编辑] 考虑对称
如果n是偶数，第一行枚举前一半的数，这样每搜索出一种方案后，沿中线对称过来又是一种方案，并且因为第一行的数小于一半，对称过来的方案总大于原方案（即在搜索树中后被搜索到），不会出现重复的情况。
如果n是奇数，先在中间行和中间列放子，并且位置都不超过半数(<n div 2)，且中间行>中间列，这样每搜索出一种方案，把它对称旋转后一共有8种方案，因为中间行和中间列的的不出现重复，所以8种方案不重复。这样只需枚举原来的1/8就可以了。 这样就完全可以过了。{注意放在正中间位置的时候}
[编辑] 使用链表
还可以再优化，用链表（或用数组模拟）记录每行待选的位置，进行插入和删除，这样就不用记录横行是否被攻击了，并且每次枚举位置的个数减少。
[编辑] 最后一位算出来
由于n行每一行都要有一个，那么所有的皇后的位置之和必然为n×(n+1)/2，在dfs的时候记录已经枚举的皇后位置之和，那么最后一个可以直接算出来。这样的话最后一个点0.907s。
[编辑] DFS+位运算
可以考虑将问题分为两个子问题来处理:
a)求n皇后具体的方案;
b)求n皇后方案的个数;
对于问题a,因为只取前三个,用最简单的DFS即可办到.
对于问题b,可以考虑采用位运算,来递归模拟试放(考虑的条件与DFS类似),但不用储存具体方案.
用此方法通过全部数据耗时约0.4secs.源码
（根据位运算的具体操作细节时间还可以更快。我的是0.2左右--Ronice 23:23 2007年9月4日 (CST)）
详细的位运算细节见matrix67的Blog:http://www.matrix67.com/blog/archives/266
