首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。