首页 > itarticle > 【leetcode】 n

【leetcode】 n

admin 11月 13, 2020 0

地址

https://leetcode.com/problems/n-queens-ii/description/

题目

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

思路

和前一道一摸一样的暴力题

代码

class  {
public:
    int n,ul[100],ux[100],uy[100],ans=0;
    char mp[100][100];
    
    void dfs(int x)
    {
        if(x==n)
        {
            ans++;
            return ;
        }
        for(int j=0;j<n;j++)
        if(ul[j]==0&&ux[j-x+50]==0&&uy[n-x-j+50]==0)
        {
            ul[j]=ux[j-x+50]=uy[n-x-j+50]=1;
            dfs(x+1);
            ul[j]=ux[j-x+50]=uy[n-x-j+50]=0;
        }
    }
    int totalNQueens(int N) {
         n=N;
        memset(ul,0,sizeof ul);
        memset(ux,0,sizeof ux);
        memset(uy,0,sizeof uy);
        dfs(0);
        return ans;
    }
};