首页 > 代码库 > 【LeetCode】N-Queens II

【LeetCode】N-Queens II

N-Queens II

Follow up for N-Queens problem.

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

 

其实比N-Queens更简单,免去了从vector<int>到vector<string>的转换,直接返回result.size()即可

class Solution {public:    int totalNQueens(int n) {        vector<vector<int> > result;    //全局变量        vector<int> cur;                //递归栈中的变量        solve(result, cur, n);            //符合条件的cur加入result        return result.size();    }    void solve(vector<vector<int> > &result, vector<int> cur, int n)    {        if(cur.size() == n)        {//找到解            result.push_back(cur);        }        else        {            for(int i = 0; i < n; i ++)            {//尝试所有可能                cur.push_back(i);                if(isValid(cur))                {//可行则递归下去                    solve(result, cur, n);                }                cur.pop_back();            }        }    }    bool isValid(vector<int> &cur)    {//针对新加点进行验证        int sz = cur.size();        int row = sz-1;            //新加点的行数sz-1        int col = cur[sz-1];    //列数cur[sz-1]        for(vector<int>::size_type st = 0; st < sz-1; st ++)        {    //验证同列错误(由于数组下标不同,同行错误不存在)            if(col == cur[st])                return false;            //验证同对角线错误            if(abs(row-st)==abs(col-cur[st]))                return false;        }        return true;    }};

【LeetCode】N-Queens II