写了一个Queens的backtrack 大牛帮我看看 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

写了一个Queens的backtrack 大牛帮我看看

写了一个Queens的backtrack 大牛帮我看看# JobHunting - 待字闺中

C*U2012-11-06 08:11

1 楼

如果用的是vector而不是数组的话无法通过online judge large
哪里可以再优化一下啊？
谢谢了
int placeQueens(int n) {
int count = 0;
int *positions = new int[n];
int p = 0;
positions[p] = 0;
int i = 0;
while(!(p == -1 && i == n)) {
bool flag = true;
while(flag && i < n) {
int j = 0;
while(j < p + 1) {
if(positions[j] == i || positions[j] - i == j - (p + 1)||
positions[j] - i == p + 1 - j) {
break;
}
else {
j++;
}
}
if(j == p + 1) {
flag = false;
}
else {
i++;
}
}
if(i == n) {
if(p > -1 && positions[p] == n - 1) {
p--;
}
else if(p == -1) {
break;
}
else {
i = positions[p--] + 1; }
}
else {
positions[++p] = i;
i = 0 ;
}
if(p + 1 == n) {
count++;
i = positions[p] + 1;
p--;
}
}
return count;
}

l*i2012-11-06 08:11

2 楼

You passed large n=12 by using the backtracking code above?

C*U2012-11-06 08:11

3 楼

yes. you can try it.
but not perfect.
used 900 millisecond

【在 l***i 的大作中提到】

: You passed large n=12 by using the backtracking code above?

c*92012-11-06 08:11

4 楼

刚刚写的，不知道算是DP还是recursive，基本上是brute force
bool checkpos(vector& cur, int pos)
{
for(int i=0;i {
for(int j=0;j{
if(cur[i][j] =='Q')
{
if(j==pos)
{
return false;
}
else if(i+j == pos + cur.size())
{
return false;
}
else if(i-j == cur.size()-pos)
{
return false;
}
}
}
}
return true;

}
void help(vector >& result, int currentnum, vector<
string>& current,int n)
{
if(currentnum == n)
{
result.push_back(current);
}
string s = "";
for(int i=0;i{
s+=".";
}
for(int i=0;i{
if(checkpos(current,i))
{
s[i] = 'Q';
current.push_back(s);
s[i] = '.';
help(result,currentnum+1,current,n);
current.pop_back();
}
}
}
vector > solveNQueens(int n) {
vector > result;
vector current;
help(result,0,current,n);
return result;
}