首页 > 代码库 > 【leetcode】N-queens II
【leetcode】N-queens II
问题:
返回N皇后问题解的个数。
分析:
详见 N-queens
实现:
bool nextPermutation(vector<int> &num) { int i = num.size() - 1; while (i >= 1) { if(num[i] > num[i - 1]) { --i; int ii = num.size() - 1; while (ii > i && num[ii] <= num[i]) --ii; if(ii > i) { swap(num[i], num[ii]); reverse(num.begin() + i + 1, num.end()); return true; } } else --i; } return false; } bool check(vector<int> &grids) { int len = grids.size(); for (int i = 0; i < len; ++i) for (int j = i + 1; j < len; ++j) { if(abs(i - j) == abs(grids[i] - grids[j])) return false; } return true; } int totalNQueens(int n) { if(n < 1) return 0; if(n == 1) return 1; int total = 0; //init the girds. vector<int> grids(n,0); for (int i = 0; i < n; ++i) { grids[i] = i; } while (nextPermutation(grids)) { if(check(grids)) total++; } return total; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。