A 0 ms C++ solution


  • 0

    This idea is learned from other's, easy to understand and really good solution.

    void procedure(int &res, vector<int> &isvalid, int i, int n)//res用引用,表示res唯一只有一个
    {
    	if (i == n)
    	{
    		++res;
    		return;
    	}
    	int j;
    	for (j = 0; j < n; ++j)
    	{
    		if (isvalid[j] && isvalid[n + i + j] && isvalid[4 * n - 2 - i + j])
    		{
    			isvalid[j] = isvalid[n + i + j] = isvalid[4 * n - 2 - i + j] = 0;
    			procedure(res, isvalid, i + 1, n);
    			isvalid[j] = isvalid[n + i + j] = isvalid[4 * n - 2 - i + j] = 1;
    		}
    	}
    	return;
    }
    int totalNQueens(int n) 
    {
    	if (!n)
    		return 0;
    	int res = 0;
    	vector<int> isvalid(n + 2 * (2 * n + 1), 1);
    	procedure(res, isvalid, 0, n);
    	return res;
    }

  • 0

    Good goodGood goodGood goodGood goodGood goodGood goodGood good


  • 0
    P

    I cheated...

    int totalNQueens(int size, int layerNum=0, int left=0, int right=0, int stay=0) {
        int mask = left | right | stay;
    	int ret = 0;
    
    	while (mask != (1<<size)-1) {
    		int cand = (~mask) & ~((~mask) - 1);
    		if (layerNum != size - 1) {
    			int nxtLayer = totalNQueens(size, layerNum + 1, ((left | cand) << 1)&((1 << size) - 1), ((right | cand) >> 1)&((1 << size) - 1), stay | cand );
    			ret += nxtLayer;
    		}
    		else ++ret;
    		mask = (mask | cand);
    	}
    	return ret;
    }

Log in to reply
 

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