题解 | #N皇后问题#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */

    bool isValid(vector<int> &pos, int row, int col)
    {
        // 遍历所有已记录的行
        for(int i=0; i<row; ++i)
        {
            // 不能同行同列和同一斜线
            // pos下班为行号，元素为列号，即已经选择的位置;
            // 同一斜线指的是45°的斜线;
            if(row==i || col==pos[i] || abs(row-i)==abs(col-pos[i]))
                return false;
        }

        return true;
    }

    // 递归查找皇后种类
    void recursion(int n, int row, vector<int>& pos, int &res)
    {
        // 全部行都选择了位置
        if(row==n)
        {
            ++res;
            return;
        }

        // 遍历当前行的所有列，找到当前行满足条件的列;
        for(int j=0; j<n; ++j)
        {
            if(isValid(pos, row, j))
            {
                // 加入当前位置
                pos[row] = j;
                // 找到之后继续遍历下一行
                recursion(n, row+1, pos, res);
            }
        }
    }


    int Nqueen(int n) {
        // write code here
        int res = 0;
        //下标为行号，元素为列号，记录皇后位置
        vector<int> pos(n, 0);
        // 递归
        recursion(n, 0, pos, res);

        return res;
    }
};