description:

八皇后
Note:

Example:

Example:Input: 4 Output: [[".Q..", // Solution 1"...Q","Q...","..Q."],["..Q.", // Solution 2"Q...","...Q",".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

answer:

class Solution { public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> res;vector<string> queens(n, string(n, '.')); //string(int n,char c); //用n個字符c初始化helper(0, queens, res);return res;}void helper(int curRow, vector<string>& queens, vector<vector<string>>& res) {int n = queens.size();if (curRow == n) { //如果已經進行到最后一行，就證明之前都可以，那就結束了，得到了一種可能的結果res.push_back(queens);return;}for (int i = 0; i < n; ++i) {if (isValid(queens, curRow, i)) {// 在現在進行到的這一行，先假設放到現在這一行，看看如果和之前不沖突就繼續遞歸queens[curRow][i] = 'Q'; helper(curRow + 1, queens, res);queens[curRow][i] = '.';//遞歸之后發現不太行之后再重新把這個位置設置成'.',然后換一列繼續遞歸}}}bool isValid(vector<string>& queens, int row, int col) { //因為之前是就在這一行看，找一列合格的，所以不用檢查行了，這一行一定就它一個皇后for (int i = 0; i < row; ++i) {if (queens[i][col] == 'Q') return false;}for (int i = row - 1, j = col + 1; i >= 0 && j < queens.size(); --i, ++j) {if (queens[i][j] == 'Q') return false;}for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {if (queens[i][j] == 'Q') return false;}return true;} };

relative point get√：

• string(int n,char c); //用n個字符c初始化

hint :

轉載于:https://www.cnblogs.com/forPrometheus-jun/p/11241064.html

總結

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

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