C++ 12ms recursive


  • 0
    P
    typedef vector<int> vi;
    typedef vector<string> vs;
    void ray(vector<vi> &out,vi tmp,int n,int j){
        if(j==n){
            out.push_back(tmp);
            return;
        }
        vi st(n,0);
        for(int i=0;i<j;i++){
            st[tmp[i]]=1;
            if(tmp[i]+j-i<n) st[(tmp[i]+j-i)%n]=1;
            if(tmp[i]+i-j>=0) st[tmp[i]+i-j]=1;
        }
        for(int i=0;i<n;i++){
            if(st[i]==0){
                tmp[j] = i;
                ray(out,tmp,n,j+1);
            }
        }
        return;
    }
    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<vi> help;
            ray(help,vi(n,0),n,0);
            vector<vs> solu(help.size(),vs(n,string(n,'.')));
            for(int i=0;i<help.size();i++) for(int j=0;j<n;j++) solu[i][j][help[i][j]] = 'Q';
            return solu;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.