回溯 Leetcode 51 N皇后

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;
        }

        // 列col
        for(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;
    }
};

原文地址：https://blog.csdn.net/weixin_46930685/article/details/136375803

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！