首页 > 代码库 > LeetCode52 N-Queens II
LeetCode52 N-Queens II
题目:
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.(Hard)
分析:
跟昨天的题目一样的思路也能做,不知道为什么叫follow-up,明天再来研究一下解法优化。
代码:
1 class Solution { 2 private: 3 int result = 0; 4 void helper(vector<string>& v, int row, int n) { 5 for (int i = 0; i < n; ++i) { 6 v[row][i] = ‘Q‘; 7 if (isValid(v, row, i, n)) { 8 if (row == n - 1) { 9 result++;10 v[row][i] = ‘.‘;11 return;12 }13 helper(v, row + 1, n);14 }15 v[row][i] = ‘.‘;16 }17 }18 bool isValid (const vector<string>& v, int x, int y, int n) {19 for (int i = 0; i < x; ++i) {20 if (v[i][y] == ‘Q‘) {21 return false;22 }23 }24 for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--,j--) {25 if(v[i][j] == ‘Q‘) {26 return false;27 }28 }29 for(int i = x - 1, j = y + 1; i >= 0 && j < n; i--,j++){30 if(v[i][j] == ‘Q‘) {31 return false;32 }33 }34 return true;35 }36 public:37 int totalNQueens(int n) {38 vector<string> v(n, string(n, ‘.‘));39 helper(v,0,n);40 return result;41 }42 };
LeetCode52 N-Queens II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。