3ms, super fast (C++)


  • 0
    P
    class Solution {
    public:
        int upperlim, ans;
        int n;
        void dfs(int row, int ld, int rd, vector<string> &bitmap, vector<vector<string> > &res){
            int pos, p;
            if(row != upperlim){
                pos = upperlim & (~(row | ld | rd));
                while(pos){
                    p = pos & -pos;
                    pos = pos - p;
                    string line(n, '.');
                    int x = p, cc = 0;
                    while((x & 1) != 1){
                        cc++;
                        x >>= 1;
                    }
                    line[cc] = 'Q';
                    bitmap.push_back(line);
                    dfs(row | p, (ld | p) << 1, (rd | p) >> 1, bitmap, res);
                    bitmap.pop_back();
                }
            }else{
                ans++;
                res.push_back(bitmap);
            }
        }
        
        vector<vector<string>> solveNQueens(int n) {
            upperlim = (1 << n) - 1;
            ans = 0;
            this->n = n;
            vector<string> bitmap;
            vector<vector<string> > res;
            dfs(0, 0, 0, bitmap, res);
            return res;
        }
    };
    

Log in to reply
 

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