Share my 8ms c++ Solution


  • 0
    C
    //N-Queens
    class Solution {
    public:
    vector<vector<string>> solveNQueens(int n) {
    
    	vector<vector<string>> vc;
    	if (n == 0)
    		return vc;
    	vector<string> tmp(n, string(n, '.'));//nxn
    	vector<int> cols(n, -1);
    	vector<bool> mark(n);
    	for (int b = 0; b < n; b++)
    	{
    		cols[0] = b;
    		tmp[0][cols[0]] = 'Q';
    		mark[b] = true;
    		helper( 1, n, vc, tmp, cols, mark);
    		tmp[0][cols[0]] = '.';
    		cols[0] = -1;
    		mark[b] = false;
    	}
    	return vc;
    }
    private:
    void helper(int s, int e, vector<vector<string>>& vc, vector<string>& tmp, vector<int>& cols,vector<bool>& mark)
    {
    	if (s == e)
    	{
    		vc.push_back(tmp);
    		return;
    	}
    	for (int b = 0; b < e; b++)
    	{
    		//column conflict
    		if (!mark[b])
    		{
    			bool mark2 = true;
    			//diagonal conflick
    			for (int k = 0; k < s; k++)
    			{
    				if (abs(s - k) == abs(b - cols[k]))
    				{
    					mark2 = false;
    					break;
    				}
    			}
    			if (mark2)
    			{
    				cols[s] = b;
    				tmp[s][cols[s]] = 'Q';
    				mark[b] = true;
    				helper(s + 1, e, vc, tmp, cols, mark);
    				tmp[s][cols[s]] = '.';
    				cols[s] = -1;
    				mark[b] = false;
    			}
    		}
    	}
    }
    

    };


Log in to reply
 

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