Accepted 4ms c++ solution use backtracking and bitmask, easy understand.


  • 0
    A

    with reference, the program won't need to allocate memory can copy to generate a new vector<string>


  • 0
    F

    clear answer~


  • 0

    Thanks for sharing your solution. What is (and how to analyze) the time complexity of it?


  • 0
    D

    goooooood answer


  • 0
    B

    I changed the int to bool type, I thought it won't make any difference, but result shows that bool is slower (about 12ms).


  • 2

    In fact, vector<bool> is not a STL container. You should avoid to use it. You can also get the knowledge from http://stackoverflow.com/questions/17794569/why-is-vectorbool-not-a-stl-container and http://stackoverflow.com/questions/670308/alternative-to-vectorbool


  • 0
    K
    This post is deleted!

  • 0
    Y

    @qkhhly
    The time complexity of the improved solution which is the one with line indicators, is 0_1468382259321_nn.JPG


  • 0
    C
    This post is deleted!

  • 1
    E

    34 lines, 6ms. A little improvement based on your idea.
    Using an int array to record the column of queens in previous rows.

    class Solution {
    public:

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string> > res;
    	vector<string> temp(n, string(n,'.'));
    	int dp[n];
    	helper(res, temp, dp, 0, n);
    	return res;
    }
    

    private:

    void helper(vector<vector<string> > &res, vector<string> &temp, int dp[], int row, int n){
    	if(row==n){
    		res.push_back(temp);
    		return;
    	}
    	for(int col=0;col<n;++col){
    		if(valid(dp, row, col, n)){
    			dp[row]=col;
    			temp[row][col]='Q';
    			helper(res, temp, dp, row+1,n);
    			temp[row][col]='.';
    		}
    	}
    }
    
    bool valid(int dp[], int row, int col, int n){
    	for(int i=0;i<row;++i){
    		if(dp[i]==col || abs(row-i)==abs(dp[i]-col)){
    			return false;
    		}
    	}
    	return true;
    }
    

    };


  • 0
    T

    @ericxu10101 said in Accepted 4ms c++ solution use backtracking and bitmask, easy understand.:

    abs(row-i) == abs(dp[i]-col) is very smart.


Log in to reply