[Lc]51N皇后

题目

题解

这道题是很经典的一道题，思路就是dfs与回溯剪枝。这类回溯题的递归函数基本套路是这样的

判断是否终止并满足条件，满足了就加入res中
遍历每一种可能，在每一种可能中：
1. 先改变当前状态
2. 递归下一层
3. 回溯时再把状态变回去

这道题就是用的这种思想，用dfs遍历每一种情况，在放下一个皇后的时候判断该位置能否放皇后。能放的话递归下一层，有两种存储皇后的方式，用string直接存储和用数组标记每一行皇后的列数，后者在存储结果时要转化为字符串再存储，但其在判断能否放皇后的时候更加便捷。

1. string保存法

时间复杂度$O(n!)$，放置第1个皇后有n种可能的方法，放置两个皇后的方法不超过 $n(n-2)$ ，放置 3 个皇后的方法不超过 $n(n-2)(n-4)$ ，以此类推。总体上，时间复杂度为 $\mathcal{O}(N!)$.
（摘自leetcode官方题解）
空间复杂度$O(n)$

class Solution {//两个方法。1.string保存法
    vector<vector<string>> res;//存最终结果
    vector<string> queens;//存当前棋盘
public:
    //检验当前位置放皇后是否符合要求
    bool check(vector<string> queens, int row, int col, int n){
        for(int i=1; i<=row; ++i){//这里的i与row的差距，从row的上一行到第0行
            if(queens[row-i][col] == 'Q') return false;//若当前列有皇后，报错
            if(col-i>=0 && queens[row-i][col-i]=='Q') return false;//若左上角有皇后，报错
            if(col+i<n && queens[row-i][col+i]=='Q') return false;//若右上角有皇后，报错
        }
        return true;//未报错返回true
    }
    //dfs与回溯，当递归超出最后一行时将当前棋盘加入结果
    void dfs(int row, int n){
        if(row>=n){
            res.push_back(queens);
            return ;
        }
        //在当前行的每一列尝试放棋子
        for(int i=0; i<n; ++i){
            if(check(queens, row, i, n)){
                queens[row][i] = 'Q';//在row行i列放棋子
                dfs(row+1, n);//递归下一行
                queens[row][i] = '.';//回溯时将放的棋子变回'.'
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        queens = vector<string>(n,string(n,'.'));//先将棋盘均设置为空
        dfs(0, n);//从第0行开始递归
        return res;

    }
};

2. 数组保存法

这个方法用一个数组保存每个皇后所在的列，在递归完成的时候需要将结果转化为字符串，而这个方法在check的时候比较方便，只需要一句

class Solution {//两个方法。2. 数组保存法
    vector<vector<string>> res;//存最终结果
    vector<int> queensCol;//存当前棋盘每个皇后的列数
public:
    //检验当前位置放皇后是否符合要求
    bool check(vector<int> queensCol, int row, int col, int n){
        for(int i=0; i<row; ++i){//这里的i表示第i行
            //遇到同列的或者两个斜线的（斜线的按照正方形考虑，长宽一样）
            if(col == queensCol[i] || abs(row-i)==abs(col-queensCol[i])) return false;
        }
        return true;//未报错返回true
    }
    //dfs与回溯，当递归超出最后一行时将当前棋盘加入结果
    void dfs(int row, int n){
        //递归完成将结果转化为棋盘
        if(row>=n){
            vector<string> queens(n, string(n,'.'));
            for(int i=0; i<queensCol.size(); ++i){
                queens[i][queensCol[i]] = 'Q';
            }
            res.push_back(queens);
            return ;
        }
        //在当前行的每一列尝试放棋子
        for(int i=0; i<n; ++i){
            if(check(queensCol, row, i, n)){
                queensCol[row] = i;//在row行i列放棋子
                dfs(row+1, n);//递归下一行
                queensCol[row] = -1;//回溯时将放的棋子变回-1
            }
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        queensCol = vector<int>(n,-1);//先将棋盘均设置为空
        dfs(0, n);//从第0行开始递归
        return res;

    }
};

Contents

题目

题解

1. string保存法

2. 数组保存法