N皇后

Leetcode 51

學習記錄自代碼隨想錄

按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
給你一個整數 n ，返回所有不同的 n 皇后問題 的解決方案。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位。

輸入：n = 4
輸出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解釋：如上圖所示，4 皇后問題存在兩個不同的解法。

輸入：n = 1
輸出：[[“Q”]]

1 <= n <= 9

要點：1.棋盤的寬度就是for循環的長度，遞歸的深度就是棋盤的高度，這樣就可以套進回溯法的模板；
2.函數參數注意要用引用&才能夠改變原值；
2.語法錯誤注意：// for(int i = row - 1, j = col - 1; i >= 0, j >= 0; i–, j–){ 判斷條件中用’,'不等同與&&，不可混用

class Solution {
private:vector<vector<string>> result;bool check(vector<string>& chessboard, int row, int col, int n){// // 同一行檢查不用，因為一行肯定只有一個'Q'// for(int j = 0; j < n; j++){//     if(chessboard[row][j] == 'Q'){//         return false;//     }// }// 同一列檢查for(int i = 0; i < row; i++){if(chessboard[i][col] == 'Q'){return false;}}// (逆時針)135°// for(int i = row - 1, j = col - 1; i >= 0, j >= 0; i--, j--){ 判斷條件中用','不等同與&&，不可混用for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){if(chessboard[i][j] == 'Q'){return false;}}// (逆時針45°)for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){if(chessboard[i][j] == 'Q'){return false;}}return true;}// 需要用引用void backtracking(int n, int row, vector<string>& chessboard){// chessboard已經初始化故不能用其尺寸作為終止條件判斷了// if(chessboard.size() == n){if(row == n){result.push_back(chessboard);return;}// 列colfor(int col = 0; col < n; col++){if(check(chessboard, row, col, n)){chessboard[row][col] = 'Q';backtracking(n, row+1, chessboard);chessboard[row][col] = '.';}}}
public:vector<vector<string>> solveNQueens(int n) {result.clear();// chessboard 棋盤vector<string> chessboard(n, string(n, '.'));backtracking(n, 0, chessboard);return result;}
};