leetcode日记（40）N皇后

一开始没看到不能同斜线，以为只要不同行不同列就行，本来想先列出每一行的Q都不同位置的棋盘然后进行排列组合就行，后来才发现还有限制（后来又想了一下，感觉可以先用这种思路然后去除有同一斜线的棋盘摆列）

然后想到了递归，依次摆放每一行，创建vector<vector<bool>> b储存该位置是否可放置不与其他皇后冲突的皇后，每放入一个皇后，更新b

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> v;
        vector<string> s;
        vector<bool> bb(n,0);
        vector<vector<bool>> b(n,bb);
        Q(n,v,s,b,0);
        return v;
    }
    void Q(int n,vector<vector<string>> &v,vector<string> &s,vector<vector<bool>> b,int i){
        vector<bool> bbb(n,1);
        for(int k=0;k<n;k++) if(b[k]==bbb) return ;
        if(s.size()==n){v.push_back(s);return;}
        for(int j=0;j<n;j++){
            if(b[i][j]==0){
                string ss;
                cout<<i<<" "<<j<<endl;
                ss.append(j,'.');
                ss.push_back('Q');
                ss.append(n-j-1,'.');
                vector<vector<bool>> bb(b);
                for(int k=i+1;k<n;k++){
                    bb[k][j]=1;
                    if(j+k-i<n) bb[k][j+k-i]=1;
                    if(j-k+i>=0) bb[k][j-k+i]=1;
                }
                s.push_back(ss);
                Q(n,v,s,bb,i+1);
                s.pop_back();
            }
        }
    }
};

原文地址：https://blog.csdn.net/s478527548/article/details/140444700

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