题目描述

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

题目描述

所以这题正解是啥？？？我裸n皇后+判断过掉了？

#include <cstdio>  
int n,a[18][18],ans=0;  
bool r[18],x1[18*2],x2[18*2];  
void dfs(int x)  
{  
    if(x==n+1)  
    {  
        ans++;  
        return;  
    }  
    for(int i=1;i<=n;i++)  
        if(!a[x][i]&&!r[i]&&!x1[x-i+n]&&!x2[x+i])  
        {  
            r[i]=1,x1[x-i+n]=1,x2[x+i]=1;  
            dfs(x+1);  
            r[i]=0,x1[x-i+n]=0,x2[x+i]=0;  
        }  
}  
int main()  
{   
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
        for(int j=1;j<=n;j++)  
            scanf("%d",&a[i][j]);  
    dfs(1);  
    printf("%d",ans);  
}