3 ms C++ solution


  • 1
    P
    typedef vector<int> vi;
    typedef vector<bool> vb;
    typedef vector<string> vs;
    class Solution {
        vector<vb> dp;
        void wtf(vector<vi> &ans,vi cur,int k){
            if(k == cur.size()){
                ans.push_back(cur);
                return;
            }
            for(int i=0;i<cur.size();++i){
                if(dp[0][i] && dp[1][k+i] && dp[2][k-i+cur.size()]){
                    dp[0][i] = dp[1][k+i] = dp[2][k-i+cur.size()] = false;
                    cur[k] = i;
                    wtf(ans,cur,k+1);
                    dp[0][i] = dp[1][k+i] = dp[2][k-i+cur.size()] = true;
                }
            }
            return;
        }
    public:
        vector<vector<string>> solveNQueens(int n) {
            dp = vector<vb>(3,vb(2*n+1,true));
            vector<vs> config;
            vector<vi> ans;
            wtf(ans,vi(n,-1),0);
            for(auto vec:ans){
                vs tmp(n,string(n,'.'));
                for(int i=0;i<n;++i) tmp[i][vec[i]] = 'Q';
                config.push_back(tmp);
            }
            return config;
        }
    };
    

Log in to reply
 

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