C++ code, 10ms, can be used for NQueens II too


  • 0
    Z
    class Solution {
    public:
        vector<vector<string> > solveNQueens(int n) {
            vector<vector<string> > res;
            if(n<1) return res;
            if(n==1){
                vector<string> res_temp;
                string temp="Q";
                res_temp.push_back(temp);
                res.push_back(res_temp);
                return res;
            }
            int count=0;
            int flag;
            vector<int> pos(n,0);
            string dot;
            for(int i=0;i<n;i++)
            dot+=".";
            
            int now_i=1;
            while(pos[0]<n){
                flag=1;
                for(int i=0;i<now_i;i++){
                    if(!isOk(i,now_i,pos[i],pos[now_i])){
                        pos[now_i]++;
                        flag=0;
                        break;
                    }
                }
                if(flag==1){
                    if(now_i==n-1){
                        vector<string> res_temp;
                        for(int j=0;j<n;j++){
                            string dot_temp=dot;
                            dot_temp.at(pos[j])='Q';
                            res_temp.push_back(dot_temp);
                        }
                        res.push_back(res_temp);
                        count++;
                        pos[now_i]++;//notice this!
                    }
                    else{
                        now_i++;
                        pos[now_i]=0;
                    }
                }
                while(pos[now_i]==n && now_i>0){
                    pos[now_i-1]++;
                    now_i=now_i-1;
                }
            }
            return res;
        }
        
        bool isOk(int i1, int i2, int j1, int j2){
            if((i2-i1==j2-j1) || (i2-i1+j2-j1==0) || j2==j1)
            return false;
            return true;
        }
    };

Log in to reply
 

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