leetcode 51 N皇后问题

佚名 6年前 (2019-04-12) 随笔 710人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

其实就是全排列问题+剪枝，也是很经典很经典

代码：

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> pos(n,-1);//记录第i+1行的皇后，应该放在第j+1列
        int row=0;
        DFS(n,row,pos,res);
        return res;
    }
    void DFS(int n,int row,vector<int>& pos,vector<vector<string>>& res){
        //回溯法,能到下一条语句一定合法
        //递归边界1，得到最终的解；
        if(row==n){
            vector<string> temp(n,string(n,'.'));
            for(int i=0;i<n;i++){
                temp[i][pos[i]]='Q';
            }
            res.push_back(temp);
        }else{
            for(int col=0;col<n;col++){
                //新加皇后到row+1行，col+1列合法，进入子问题；如果新皇后怎么加都无效，则本次循环结束，col+1进行下一次循环
                //判断是否需要向子问题递归，不需要则返回上一层；
                if(isvalid(pos,row,col)){
                    pos[row]=col;
                    DFS(n,row+1,pos,res);
                    pos[row]=-1;
                }
            }
        }
        
    }
    bool isvalid(vector<int>& pos,int row,int col){
        //判断是否放在了已经有皇后的列上，以及是否在同一对角线上；
        for(int i=0;i<row;i++){
            if((col==pos[i])||(abs(row-i)==abs(col-pos[i])))
                return false;
        }
        return true;
    }
};