leetcode第51题：N皇后问题 [困难]

题目描述

image.png

考点

• 回溯算法

解题思路

• 使用数组：column, ldiag, rdiag 存储当前列，左对角线、右对角线是否被占用；
• 每次访问矩阵的一行，递归遍历每一列；
• 注意：nxn的矩阵，对角线数量为2xn-1

image.png

代码实现

class Solution {
private:
    void backtracking(vector<vector<string>>& ans, vector<string>& board, vector<bool>& column, 
        vector<bool>& ldiag, vector<bool>& rdiag, int row, int n){
            if(row == n){
                ans.push_back(board);
                return;
            }

            // NOTE: 左对角线，row+col相等；右对角线，n-1+row-col相等；
            for(int i = 0; i < n; i++){
                if(column[i] || ldiag[row+i] || rdiag[n-1+row-i]){
                    continue;
                }

                // 修改当前结点状态，表示已访问
                board[row][i] = 'Q';
                column[i] = ldiag[row+i] = rdiag[n-1+row-i] = true;

                // 递归遍历后续行
                backtracking(ans, board, column, ldiag, rdiag, row+1, n);

                // 回溯过程
                board[row][i] = '.';
                column[i] = ldiag[row+i] = rdiag[n-1+row-i] = false;
            }
        }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        if(n == 0)
            return ans;
        
        // board存储返回结果
        vector<string> board(n, string(n, '.'));
        vector<bool> column(n, false), ldiag(2*n-1, false), rdiag(2*n-1, false);

        // 从第0行开始递归
        backtracking(ans, board, column, ldiag, rdiag, 0, n);
        return ans;
    }
};