【LeetCode】52. N-Queens II

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

简单的回溯法。

cur[i] == j 代表第i行的皇后位于第j列。

对于每一行，尝试所有列，

如果当前行尝试的位置不与前面所有行的位置冲突，则可以递归到下一行。

class Solution {

public:

    int totalNQueens(int n) {

        int count = ;

        vector<int> cur;

        Helper(count, cur, , n);

        return count;

    }

    void Helper(int& count, vector<int> cur, int pos, int n)

    {

        if(pos == n)

            count ++;

        else

        {

            for(int i = ; i < n; i ++)

            {

                cur.push_back(i);

                if(check(cur))

                    Helper(count, cur, pos+, n);

                cur.pop_back();

            }

        }

    }

    bool check(vector<int> cur)

    {

        int size = cur.size();

        int loc = cur[size-];

        for(int i = ; i < size-; i ++)

        {

            //never same row

            //col

            if(cur[i] == loc)

                return false;

            //diag

            if(abs(cur[i]-loc) == abs(i-size+))

                return false;

        }

        return true;

    }

};

巴特西

【LeetCode】52. N-Queens II

最新文章

热门文章