题解 | #N皇后问题#

class Solution {
public:
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    void findtype(vector<vector<int>>& vv,int n,int &sum,int row,int col)
    {
        
        bool check=false;  //检查标志，为true表示或行或列或斜线上已有皇后
        for(int i=0;i<n;i++)
        {
            //判断同一行是否已有皇后
            if(vv[row][i]==1)
            {
                check=true;
                break;
            }
            
            //判断同一列是否已有皇后
            if(vv[i][col]==1)
            {
                check=true;
                break;
            }
            
            //判断斜线是否已有皇后
            if(row-i>-1&&col-i>-1&&vv[row-i][col-i]==1)
            {
                check=true;
                break;
            }
            if(row+i<n&&col+i<n&&vv[row+i][col+i]==1)
            {
                check=true;
                break;
            }
            if(row-i>-1&&col+i<n&&vv[row-i][col+i]==1)
            {
                check=true;
                break;
            }
            if(row+i<n&&col-i>-1&&vv[row+i][col-i]==1)
            {
                check=true;
                break;
            }
            
        }
        
        //符合条件
        if(check==false)
        {
            //为最后一行且满足条件
            if(row==n-1)
            {
                sum++;
                return;
            }
            else
            {
                vv[row][col]=1;
                for(int j=0;j<n;j++)
                {
                    findtype(vv,n,sum,row+1,j);
                }
                //回溯
                vv[row][col]=0;
                return;
             }
        }
        else
            return;
    }
    
    
    //递归+回溯
    int Nqueen(int n) {
        // write code here
        //棋盘上全为0表示无皇后
        vector<vector<int>> vv(n,vector<int>(n,0));
        int sum=0;
        
        //遍历第一行的每个格子，递归下去，找到合适的摆法
        for(int j=0;j<n;j++)
        {
            findtype(vv,n,sum,0,j);
        }
        
        return sum;
        
    }
};