//設(shè)置全局變量，記錄N皇后的擺放個(gè)數(shù)
int count=0;
//判斷當(dāng)前位置是否滿(mǎn)足條件，不同行，不同列也不在同一條斜線(xiàn)上
//注意，這里的參數(shù)需要已經(jīng)保存的路徑path，以及當(dāng)前的行列
bool isOK(vector<int> &path,int row,int col){
    //遍歷之前的行，判斷每行里面是否有和當(dāng)前位置沖突的皇后存在，
    //如果有，則當(dāng)前位置不能放置皇后，返回false
    for(int i=0;i<row;i++){
        //這里只需要判斷不同列的要求，因?yàn)楫?dāng)前行還沒(méi)有放置元素
        //而且遞歸回溯調(diào)用確保每行只選取一個(gè)皇后
        //此外需要判斷兩條斜對(duì)角線(xiàn)上是否存在皇后
        //兩條對(duì)角線(xiàn)上的元素分別和相等，以及差值相等，據(jù)此可以判斷對(duì)角線(xiàn)元素
        if(col==path[i]||i+path[i]==row+col||i-path[i]==row-col)
            return false;
    }
    //當(dāng)循環(huán)結(jié)束依然沒(méi)有返回時(shí)，說(shuō)明之前行的皇后與當(dāng)前位置不沖突，返回true
    return true;
}
//遞歸回溯操作，每次一行（一層，深度+1）
//此時(shí)的參數(shù)，需要傳遞已經(jīng)保存的行列位置
//以及網(wǎng)格的大小和當(dāng)前行，用于遞歸的跳出，并進(jìn)行下一次遞歸
//這里的row和組合里的start作用挺相似的，不對(duì)
//感覺(jué)這里的row是可以省略的，和排列問(wèn)題里的deepth是相似的
//row可以使用path.size()代替，
void dfs(vector<int> &path,int n){
    //遞歸終止條件，當(dāng)深度到最后一行時(shí)，說(shuō)明此時(shí)完成了一次擺放方式
    //計(jì)數(shù)+1，直接返回，也可以使用path的大小判斷
    if(path.size()==n){
        count++;
        return ;
    }
    //for循環(huán)遍歷path.size()行的列元素，
    //也就是在path.size()行選取有效的位置
    for(int i=0;i<n;i++){
        //判斷當(dāng)前位置（path.size(),i）是否為有效位置
        //如果不是則選擇下一列繼續(xù)測(cè)試，直到找到有效位置
        //如果全部位置都不合適，就不會(huì)進(jìn)行下一層的搜索，直接返回上一層繼續(xù)循環(huán)
        //這里循環(huán)結(jié)束也能跳出遞歸
        if(!isOK(path,path.size(),i)){
            continue;                
        }
        //將找到的合適位置存儲(chǔ)起來(lái)，其中下標(biāo)表示行數(shù)，值表示列數(shù)
        path.push_back(i);
        //遞歸進(jìn)入下一次
        dfs(path,n);
        //回溯操作
        path.pop_back();
    }
}
int Nqueen(int n) {
    //這個(gè)變量用于存儲(chǔ)每行中選取的列數(shù)值
    //形象點(diǎn)描述就是每層選的數(shù)值
    vector<int> path;
    //調(diào)用遞歸函數(shù)
    dfs(path, n);
    //返回結(jié)果
    return count;
}