题解 | #N皇后问题#

class Solution {
public:
    bool check(int x,int y,vector<vector<bool>>&f,int n)
    {
        bool fl=true;
        for(int i=1;i<=x;i++)if(f[i][y])fl=false;
        int i=x-1,j=y-1;
        while(i>=1&&i<=n&&j>=1&&j<=n)
        {
            if(f[i][j])
            {
                fl=false;
                break;
            }
            i--,j--;
        }
        i=x-1,j=y+1;
        while(i>=1&&i<=n&&j>=1&&j<=n)
        {
            if(f[i][j])
            {
                fl=false;
                break;
            }
            i--,j++;
        }
        return fl;
    }
    void dfs(int &res,vector<vector<bool>>f,int row,int n)
    {
        if(row>n)
        {
            res++;
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(check(row,i,f,n))
            {
                f[row][i]=true;
                dfs(res,f,row+1,n);
                f[row][i]=false;
            }
        }
    }
    int Nqueen(int n) {
        vector<vector<bool>>f(n+2,vector<bool>(n+2,false));
        int res=0;
        dfs(res,f,1,n);
        return res;
    }
};