C***U
发帖数: 2406 | 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***i
发帖数: 1309 | 2 You passed large n=12 by using the backtracking code above? |
C***U
发帖数: 2406 | 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****9
发帖数: 164 | 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;
} |
b*****x
发帖数: 48 | 5 为什么不算perfect?
【在 C***U 的大作中提到】
: yes. you can try it.
: but not perfect.
: used 900 millisecond
|
C***U
发帖数: 2406 | 6 900 milliseconds
那个judge large总共也没几个例子
我不知道算不算慢
【在 b*****x 的大作中提到】
: 为什么不算perfect?
|
