20 line, 4ms c++ solution, using bitmap


  • 3
    S
    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<string> curRes(n, string(n, '.'));
            vector<vector<string>> finalRes;
            dfs(curRes, 0, n, 0, 0, 0, finalRes);
            return finalRes;
        }
        void dfs(vector<string> &curRes, int line, int n, int a, int b, int c, vector<vector<string>> &finalRes){
            if(n==line){
                finalRes.push_back(curRes);
                return;
            }
            for(int i=0;i<n;++i){
                if( (a&(1<<i)) || (b&(1<<(i+line))) || (c&(1<<(n-1+i-line))) ) continue;
                curRes[line][i]='Q';
                dfs(curRes, line+1, n, a|(1<<i), b|(1<<(i+line)), c|(1<<(n+i-1-line)), finalRes);
                curRes[line][i]='.';
            }
        }
    };

  • 0
    K

    what if n is greater than 32? int numbers has no more than 32 bits


  • 0
    W

    @Kenigma I heard that the current limit the world has ever reached is 27


  • 0
    K

    @wl5888 you mean the computation takes forever for greater n given the current computational power?


Log in to reply
 

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