6ms C++ solution, beats 90%


  • 0
    J
    class Solution {
    public:
        vector<vector<string>> solveNQueens(int n) {
            vector<string> current(n, string(n,'.'));
            vector<vector<string>> result;
            nqueen = n;
            vector<int> colume(n, 0);
            vector<int> diag(2*n-1, 0);
            vector<int> antidiag(2*n-1, 0);
            nQueensHelper(result, current, colume, diag, antidiag, 0);
            return result;
        }
        
        bool nQueensHelper(vector<vector<string>> & result, vector<string> & current, vector<int> & colume, 
            vector<int> & diag, vector<int> & antidiag, int q) {
            
            if (q >= nqueen) {
                result.push_back(current);
                return true;
            }
            
            for (int i = 0; i < nqueen; i++) {
                if (colume[i]==0 && diag[i+q]==0 && antidiag[nqueen-i-1+q]==0) {
                    current[q][i]='Q';
                    colume[i]=1; diag[i+q]=1; antidiag[nqueen-i-1+q]=1;
                    nQueensHelper(result, current, colume, diag, antidiag, q+1);
                    current[q][i]='.';
                    colume[i]=0; diag[i+q]=0; antidiag[nqueen-i-1+q]=0;
                }
            }
            
            return false;
        }
        
        int nqueen;
    };

Log in to reply
 

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