济南学习 Day 5 T3 am

【题目描述】

　　众所不知，rly现在不会玩国际象棋。但是，作为一个OIer，rly当然做过八皇后问题.在这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在

n*n的棋盘中，摆放n个皇后使它们互相不能攻击到，求不同的解的数量，这就是经典的n皇后问题。现在问题推广n皇后问题，这个问题对你而言实

在是小菜一碟。但是因为上次rly把棋盘弄破了，又拿不出新的，所以rly打算难一点点，问题就是在破的棋盘上的n皇后问题。他想知道......（你们懂的..）

　　妻子都是相同的

【输入说明】

　　一行，一个整数N。

　　接下来N行，每行N个整数，要么为0，表示没坏，要么为1，表示坏了。

【输出说明】

　　一行，输出不同的接的数量。

【样例输入】

　　1 0 1 1

　　1 1 1 0

　　0 1 1 1

　　1 1 0 1

【样例输出】

【数据范围】

　　对于40%的数据，N<=13。

　　对于100%的数据，N<=16。

　　对于30%的数据棋盘没有破，你可以认为rly又去买了一个新的。

 /*位运算优化n皇后*/

 #include<cstdio>

 #include<iostream>

 #define N 20

 using namespace std;

 int hang[N],n,ans;

 void dfs(int t,int a,int b,int c)//a，b，c都是二进制数，表示哪一列或对角线是否放过皇后，1为放过

 {

     if(t==n+)

     {

         ans++;return;

     }

     int S=((<<n)-)&(~(hang[t]|a|b|c));

     /*

       S是一个二进制数，表示当前可以往哪一列放皇后

       (hang[t]|a|b|c)表示哪些列从列和对角线的角度来说都放过

       加上~（取反），表示哪些列可以放皇后

     */

     while(S)

     {

         int x=S&(-S);//x表示可以当前放皇后的位置

         dfs(t+,a+x,(b+x)<<,(c+x)>>);

         S-=x;

     }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       for(int j=;j<=n;j++)

       {

           int x;scanf("%d",&x);

           hang[i]+=x<<(j-);

       }

     dfs(,,,);

     printf("%d",ans);

     return ;

 }

思路：位运算优化后的n皇后问题

巴特西

济南学习 Day 5 T3 am

最新文章

热门文章