BZOJ 4809(皇后-N皇后)

Description

众所不知，rly现在不会玩国际象棋。但是，作为一个OIer，rly当然做过八皇后问题。这里再啰嗦几句，皇后可以攻击到同行同列同对角线，在n*n的方格中摆n个皇后使其互不攻击到，求不同的解的数量，这就是经典的n皇后问题。现在问题推广到n皇后问题，这个问题对于你而言实在是小菜一叠。但因为上一次rly把棋盘弄破了，又拿不出新的，所以rly打算难一点点，问题就是破棋盘上的n皇后问题。他想知道……（你们懂的）。
棋子都是相同的。
Input

一行，一个正整数N。
接下来N行，每行N个数，要么为0，表示没坏，要么1，表示坏了。
N<=16
Output

一行，输出不同的解的数量。
Sample Input

4

1 0 1 1

1 1 1 0

0 1 1 1

1 1 0 1

Sample Output

1
HINT

Source

By FancyCoder

就是个n皇后，注意常数写小

#include<bits/stdc++.h> 
using namespace std;
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
                        For(j,m-1) cout<<a[i][j]<<' ';\
                        cout<<a[i][m]<<endl; \
                        } 
#pragma
#define
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return ((a-b)%F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 

#define
int a[MAXN][MAXN]={};
bool b[MAXN]={},b1[MAXN<<1]={},b2[MAXN<<1]={};
int ans=0,n;
void dfs(int l) {
    if (l>n) {
        ++ans;return;
    }
    For(i,n) if (!a[l][i]&&!b[i]&&!b1[i+l]&&!b2[i-l+n]){
        b[i]=b1[i+l]=b2[i-l+n]=1;
        dfs(l+1);
        b[i]=b1[i+l]=b2[i-l+n]=0;
    }
}
int main()
{
//  freopen("bzoj4809.in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();
    For(i,n) For(j,n) a[i][j]=read();
    dfs(1);
    cout<<ans<<endl;
    return 0;
}