class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<vector<string>> xxx;
vector<vector<int> > res;
vector<int> com;
int len=n;
c3(res,com,n,len,0);
hua(xxx,res,len);
return xxx;
}
private:
void c3(vector<vector<int> > &res,vector<int> &com,int n,int len,int begin)
{
if(len == 0 && judge(com))
{
res.push_back(com);
return ;
}
for(int i=0;i<n&&len>0;++i)
{
com.push_back(i);
if(judge(com)) //剪枝，没有的话会超时
c3(res,com,n,len-1,i);
com.pop_back();
}
}
bool judge(vector<int> &com)
{
for(int i=0;i<com.size();i++)
{
for(int j=i+1;j<com.size();j++)
{
if(com[i] == com[j] || abs(i-j) == abs(com[i]-com[j]))
return false;
}
}
return true;
}
void hua(vector<vector<string>> &str,vector<vector<int>> &com,int len)
{
for(auto c:com)
{
vector<string> ge;
for(auto d:c)
{
string tem="";
for(int i=0;i<len;++i)
{
if(i==d)
tem +="Q";
else
tem +=".";
}
ge.push_back(tem);
}
str.push_back(ge);
}
}
};
但44ms
转载于:https://www.cnblogs.com/yanqi110/p/4931158.html
