52. N-Queens II
难度:Hard
刷题内容
原题连接
- https://leetcode.com/problems/n-queens-ii/
内容描述
The n-queens puzzle is the problem of placing n queens on an n¡Án chessboard such that no two queens attack each other.
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
Example:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
˼·1 **- ʱ¼ä¸´ÔÓ¶È: O(2^n)*- ¿Õ¼ä¸´ÔÓ¶È: O(n)***
ÕâÌâºÍÉÏÒ»µÀÌâ»ù±¾Ò»Ñù£¬Ö»ÊÇÇó´ÎÊý¡£ÉÔ΢¸Ä¶¯Ò»Ï¾ͺ㬾ßÌåµÄ²»¶à˵ÁË
class Solution {
public:
int travel(int* d,int level,int n,int* l,int* r)
{
if(level >= n)
return 1;
int ans = 0;
for(int i = 0;i < n;++i)
if(!d[i] && !r[level + i] && !l[i - level + n])
{
d[i] = 1;
r[level + i] = 1;
l[i- level + n] = 1;
ans += travel(d,level + 1,n,l,r);
d[i] = 0;
r[level + i] = 0;
l[i- level + n] = 0;
}
return ans;
}
int totalNQueens(int n) {
int d[n];
int l[2 * n];
int r[2 * n];
memset(d,0,sizeof(d));
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
int ans = 0;
for(int i = 0;i < n;++i)
{
d[i] = 1;
r[i] = 1;
l[i + n] = 1;
ans += travel(d,1,n,l,r);
d[i] = 0;
r[i] = 0;
l[i + n] = 0;
}
return ans;
}
};
