首页 > 代码库 > n皇后问题的递归和迭代版 leetcode N-Queens
n皇后问题的递归和迭代版 leetcode N-Queens
题目如下图：
递归版
class Solution {public: vector<vector<string>> solveNQueens(int n) { vector<int> dict(n, 0); dfs(0, dict, n); return res; }private: void dfs(int cur, vector<int> & dict, int n) { if (cur == n) { fillRes(dict); return; } for (int i = 0; i < n; i++) { dict[cur] = i; if (check(dict, cur)) dfs(cur + 1, dict, n); } } void fillRes(vector<int> & dict) { vector<string> tmp; for (int i = 0; i < dict.size(); i++) { string s(dict.size(), ‘.‘); s[dict[i]] = ‘Q‘; tmp.push_back(s); } res.push_back(tmp); } bool check(vector<int> & dict, int cur) { for (int i = 0; i < cur; i++) { if (dict[i] == dict[cur] || abs(dict[cur] - dict[i]) == abs(cur - i)) return false; } return true; } vector<vector<string>> res;};
迭代版
class Solution {public: vector<vector<string>> solveNQueens(int n) { vector<vector<string>> res; vector<int> nums(n, 0); int cur = 0; while (cur >= 0) { if (check(nums, cur)) cur = cur + 1; else { int carry = 1; for (; cur >= 0 && carry != 0;) { nums[cur] += carry; if (nums[cur] == n) { nums[cur--] = 0; carry = 1; } else { carry = 0; } } } if (cur == n) { fillRes(res, nums); int carry = 1; for (cur--; cur >= 0 && carry != 0;) { nums[cur] += carry; if (nums[cur] == n) { nums[cur--] = 0; carry = 1; } else { carry = 0; } } } } return res; }private: void fillRes(vector<vector<string>> & res, vector<int> & dict) { vector<string> tmp; for (int i = 0; i < dict.size(); i++) { string s(dict.size(), ‘.‘); s[dict[i]] = ‘Q‘; tmp.push_back(s); } res.push_back(tmp); } bool check(vector<int> & dict, int cur) { for (int i = 0; i < cur; i++) { if (dict[i] == dict[cur] || abs(dict[cur] - dict[i]) == abs(cur - i)) return false; } return true; }};
n皇后问题的递归和迭代版 leetcode N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。