1 題目

n?皇后問題 研究的是如何將 n?個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回所有不同的?n?皇后問題 的解決方案。

每一種解法包含一個不同的?n 皇后問題 的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

2 解法

以行 為遍歷單位, 依次確定每行的Q的列數, 并用位運算的方式記錄每個列, 兩條斜線是否已經被占用, 并用遞歸(感覺不用遞歸也可以, 畢竟是二維的)的方式調用下一行, 至于回溯的方式就是, 當行的每一個列完成后要把其位置退出來:

class Solution { public:int Q_num;int col;int row_plus_col;int row_col_plus_n_1;void do_flip(int r_idx, int c_idx){col ^= (1 << c_idx);row_plus_col ^= (1 << (r_idx + c_idx));row_col_plus_n_1 ^= (1 << (r_idx - c_idx + Q_num - 1));}void dfs(vector<pair<int, int>> &tmp_Q_pos, vector<vector<pair<int, int>>> &all_Q_pos, int cur_r_idx) {if (cur_r_idx == Q_num) {all_Q_pos.push_back(tmp_Q_pos);return;}int c_idx = 0;while (c_idx < Q_num) {if ((col & (1 << c_idx)) == 0 &&(row_plus_col & (1 << (cur_r_idx + c_idx))) == 0 &&(row_col_plus_n_1 & (1 << (cur_r_idx - c_idx + Q_num - 1))) == 0) {do_flip(cur_r_idx, c_idx);tmp_Q_pos.push_back(make_pair(cur_r_idx, c_idx));dfs(tmp_Q_pos, all_Q_pos, cur_r_idx + 1);tmp_Q_pos.pop_back();do_flip(cur_r_idx, c_idx);}c_idx ++;}}vector<vector<string>> solveNQueens(int n) {Q_num = n;col = 0;row_plus_col = 0;row_col_plus_n_1 = 0;vector<vector<pair<int, int>>> all_Q_pos;vector<pair<int, int>> tmp_Q_pos;dfs(tmp_Q_pos, all_Q_pos, 0);vector<vector<string>> all_res(all_Q_pos.size(), vector<string>(n, string(n, '.')));for (int res_index = 0; res_index < all_Q_pos.size(); res_index ++) {for_each(all_Q_pos[res_index].begin(), all_Q_pos[res_index].end(), [&](auto pair){all_res[res_index][pair.first][pair.second] = 'Q';});}return all_res;} };

?

總結

以上是生活随笔為你收集整理的leetcode51 --- solveNQueens的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。