快捷搜索: 长连接 前端 源码 pan

(90)51. N 皇后(leetcode).

题目链接:
https://leetcode-cn.com/problems/n-queens/
难度:困难
51. N 皇后
	n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
	给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
	每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 Q 和 . 分别代表了皇后和空位。
提示:
	皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。

n皇后问题 额 曾经还年轻的时候写过 回溯嘛 很常用的思路 但是在写的时候出问题了! 我不知道怎么判断是否在同一对角线上了 。。。 首先明确 回溯法 使用集合 unordered_set <int> 保证不在同一列和同一斜线(stl还是用的少。。。) columns 保证不在同一列上 diagonal 保证不在同一正斜线上 backdiagonal 保证不在同一反斜线上 (md 我一开始想用queue 实现回溯的 结果越写越乱 然后看的题解 我好菜啊。。。)

class Solution {
          
   
public:
    vector<vector<string>> solveNQueens(int n) {
          
   
    	// ans 返回
        vector<vector<string>> ans;
        // queens 记录本次的答案
        vector<int> queens(n,-1);
        unordered_set<int> columns;
        unordered_set<int> diagonal;
        unordered_set<int> backdiagonal;
        solve(ans,queens,n,0,columns,diagonal,backdiagonal);
        return ans;
    }

    void solve(vector<vector<string>>& ans,vector<int>& queens,int n,int row,unordered_set<int>& columns,unordered_set<int>&   diagonal, unordered_set<int> &backdiagonal){
          
   
        if(row==n){
          
   
        	// 结束 答案正确
            vector<string> s=getans(queens, n);
            ans.push_back(s);
        }else{
          
   
        	// 第row行的n种情况(列)
            for(int i=0;i<n;++i){
          
   
            	// 行 斜线
                if(columns.find(i)!=columns.end()){
          
   
                    continue;
                }
                int diag=row-i;
                if(diagonal.find(diag)!=diagonal.end()){
          
   
                   continue;
                }
                int backdiag=row+i;
                if(backdiagonal.find(backdiag)!=backdiagonal.end()){
          
   
                   continue;
                }
                // queens 集合
                queens[row]=i;
                columns.insert(i);
                diagonal.insert(diag);
                backdiagonal.insert(backdiag);
                solve(ans,queens,n,row+1,columns,diagonal,backdiagonal);
                // 去除 保证下次递归正确
                queens[row]=-1;
                columns.erase(i);
                diagonal.erase(diag);
                backdiagonal.erase(backdiag);
            }

        }
        
    }
	// queens记录位置 转化为vector<string>
    vector<string> getans(vector<int> &queens,int n){
          
   
        vector<string> ans;
        for(auto a:queens){
          
   
            string s=string(n, .);
            s[a]=Q;
            ans.push_back(s);
        }
        return ans;
    }

};

还有个更好的查询方法 (大佬nb 我是想不出来的菜鸟 ) 使用二进制数 记录个坐标 写的还很清楚 (我感觉我会忘记的。。。) 不过设置为 int 最大长度就是64了吧

将数值(int) 写为 2 进制的 每一位代表该行的一个位置(0代变可以  1代表不可)
columns  保证不在同一列上  
diagonal    保证不在同一正斜线上 
backdiagonal   保证不在同一反斜线上
对于 diagonal   backdiagonal ,下一行的不能放皇后的位置是上一行的 diagonal 左移 和 backdiagonal 的右移
x & (−x) 可以获得 x 的二进制表示中的最低位的 1 的位置
x & (x−1) 可以将 x 的二进制表示中的最低位的 1 置成 0
class Solution {
          
   
public:
    vector<vector<string>> solveNQueens(int n) {
          
   
        vector<vector<string>> ans;
        vector<int> queens(n,-1);
        solve(ans,queens,n,0,0,0,0);
        return ans;
    }

    void solve(vector<vector<string>>& ans,vector<int>& queens,int n,int row,int columns,int diagonal, int backdiagonal){
          
   
        if(row==n){
          
   
            vector<string> s=getans(queens, n);
            ans.push_back(s);
        }else{
          
   
            int pos=((1<<n)-1)&(~(columns|diagonal|backdiagonal));
            while(pos!=0){
          
   
                int postion=pos&(-pos);
                pos=pos&(pos-1);
                int column=__builtin_ctz(postion);
                queens[row]=column;
                solve(ans,queens,n,row+1,columns|postion,(diagonal|postion)>>1,(backdiagonal|postion)<<1);
                queens[row] = -1;
            }
        }
        
    }

    vector<string> getans(vector<int> &queens,int n){
          
   
        vector<string> ans;
        for(auto a:queens){
          
   
            string s=string(n, .);
            s[a]=Q;
            ans.push_back(s);
        }
        return ans;
    }

};
经验分享 程序员 微信小程序 职场和发展