首页 > 代码库 > SGU 224.Little Queens

SGU 224.Little Queens

时间限制:0.75s

空间限制:6M

题意

      n*n(n<=10)的棋盘,求出放置m(m<=n*n)个皇后的方案数。

 

 


 

 

Solution:

             状态压缩+位运算  搜索。

             首先我们从上往下逐行放置,  

             DFS(line, row, l, r, k)

             line :当前行号

             row:列状态

             l:\ 左上对角线状态

             r:/右上对角线状态

             k:已放置棋子数

 

             对于每一行有不放或者放一个棋子两种方案

             放一个棋子时又要考虑哪些位置可以放置,

             

             状态压缩(row,r,l):

                       例如当n=4时

                       二进制数 

                                1=(0001)2代表在第一个位置放置了棋子

                                同理(1111) 代表已经放满;

                     

                       可放状态(pos):

                         15=(1111)代表全部位置可放

 

                         1=(0001) 代表右边第一个位置可放

 

                         0=(0000)代表无法再放

 

             

               对(pos=~(l | row | r))   pos得到当前行所有可放置的位置(可以自己模拟一下)

               

               数状数组中出现的 p= pos& - pos 得到最后一个1 的位置,即一个可放位置。

              

              状态(row,l,r  )|  p 时,即更新当前行放置后的三个状态

                     例如  p=1(0001),当前放右一;

                            row=8(1000),左一已不可放。

                            row=p | row=9(1001),  即右一和左一都不可以再放         

 

 

             当line+1,即搜索下一行时,l和r变化

             以左上对角线状态l为例

             初始为(0000)

             当右2放置1个棋子时,当前行(0010)

             由于是左上对角线,下一行l变为(0001),即 l>>1;

             r同理,即r<<1.

  

             row列状态在行变化的时候不需要更新  

             

 

 

代码

 60ms+2KB  Accepted

 

#include <cstdio>int n, sum, max, k, m;void dfs (int line , int row, int l, int r, int k) {	int pos, p, i;	if (line > n){              if(k == m) sum++;		return;	}	dfs (line + 1, row, l>>1, r<<1, k);	if (row != max) {		pos = max & (~ (row | l | r) );		while (pos != 0) {			p = pos & -pos;			pos = pos - p;			dfs (line+1,row | p, (l | p) >> 1, (r | p) << 1, k + 1);		}	}}int main() {	scanf ("%d %d", &n, &m);	max = (1 << n) - 1;	dfs (1, 0, 0, 0, 0);	printf ("%d", sum);}