题目

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

分析

只需要输出N皇后问题的解决方案的个数，只需要将上一题的代码拿来直接用即可。

int a[1000][1000];
//judge if(x,y)could be 1 in a[][]
bool place(int x,int y,int n)
{
    int i=0,j=0;
    for(i=0;i<x;i++)
        if(a[i][y]==1)  return false;
    i=x-1;j=y-1;
    while(i>=0&&j>=0)
    {
        if(a[i][j]==1)return false;
        i--;j--;
    }
    i=x-1;j=y+1;
    while(i>=0&&j<n)
    {
        if(a[i][j]==1)return false;
        i--;j++;
    }
    return true;
}
void huisu(int no,int n,int *returnSize)
{
    if(no==n-1)
    {
        for(int i=0;i<n;i++)
        {
            if(place(n-1,i,n)==true)
            {
                a[n-1][i]=1;
                *returnSize=*returnSize+1;
                a[n-1][i]=0;
            }
        }
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(place(no,i,n)==true)
            {
                a[no][i]=1;
                huisu(no+1,n,returnSize);
                a[no][i]=0;
            }
        }
    }
}


int totalNQueens(int n) {
    if(n==0)return 1;
    int returnSize=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            a[i][j]=0;
    }
    huisu(0,n,&returnSize);
    return returnSize;
}