n 皇后问题研究的是如何将 n 个皇后放置在 n*n 的棋盘上, 并且使皇后彼此之间不能相互攻击.
给定一个整数 n, 返回所有不同的 n 皇后问题的解决方案.
- https://leetcode-cn.com/problems/n-queens/
- class Solution {
- public:
- vector<vector<string>> ans;
- vector<int> queue;
- vector<vector<string>> solveNQueens(int n) {
- queue.resize(n, 0);
- dfs(n, 0, 0, 0, 0);
- return ans;
- }
- void dfs(int n, int row, int col, int ld, int rd) {
- if (row>= n) {
- add(queue, n);
- return;
- }
- int bits = ~(col | ld | rd) & ((1 <<n) - 1);
- while (bits> 0) {
- int pick = bits & (-bits);
- queue[row] = __builtin_ffs(pick) - 1;
- dfs(n, row + 1, col | pick, (ld | pick) <<1, (rd | pick)>> 1);
- bits = bits & (bits - 1);
- }
- }
- void add(vector <int> &queue, int n) {
- vector <string> tmp;
- for (int i = 0; i < n; i++) {
- string s(n, '.');
- s[queue[i]]= 'Q';
- tmp.push_back(s);
- }
- ans.push_back(tmp);
- }
- };
来源: http://www.bubuko.com/infodetail-3683693.html