Как оптимизировать алгоритм для проблем с N Queens, похожей на проблему (с ладьями и другой целью)? ⇐ C++

[Anonymous]

Проблема: < /p>

У вас есть Q Queens и R Rooks на доске с сторонами длины (R+Q) ≤ 8, и вам нужно разместить все кусочки, чтобы ни одна из них не атаковало какую -либо другую часть. Каждый квадрат на плате имеет оценку, который вы получаете, поместив пьесу в этом квадрате. Поместил ладья). Проблема в том, что мой код медленнее, чем необходимо. Я застрял в своем нынешнем подходе, и в данный момент мне больше ничего не происходит. Я не хочу тратить все свое время на такую ​​простую проблему.
Некоторые идеи, которые у меня были,:

[*] Использование целых чисел (битсетс) вместо вектора Bools (не сильно менял).
обращается с вектором , а не выполнять их, а не выполнять их, а не выполнять их. /> Избегайте размещения одних и тех же кусочков в отдельном порядке (запустите петлю at (i, j), а не в (0, 0)). < /li>
< /ul>
Это моя попытка: < /p>
#include
#include

using namespace std;

// Time Limit Error

int res = 0;
vector pts;
int N;

inline int getD1(int i, int j){
return i - j + N - 1;
}

inline int getD2(int i, int j){
return i+j;
}

void DFSR(int i, int j, int sum, int R, vector & fbI, vector & fbJ, vector & fbD1, vector & fbD2){
if (j!=-1){
fbI = true;
fbJ[j] = true;
}

if (R==0){
res = max(res, sum);

if (j != -1){
fbI = false;
fbJ[j] = false;
}
return;
}

for (int I=i; I < N; ++I){
if (fbI) continue;

for (int J=0; J= 0){
fbI = false;
fbJ[j] = false;
}
}

void DFSQ(int i, int j, int sum, int R, int Q, vector & fbI, vector & fbJ, vector & fbD1, vector & fbD2){
if (j != -1){
fbI = true;
fbJ[j] = true;

fbD1[getD1(i,j)] = true;
fbD2[getD2(i,j)] = true;
}

if (Q==0){
DFSR(0, -1, sum, R, fbI, fbJ, fbD1, fbD2);

if (j != -1){
fbI = false;
fbJ[j] = false;

fbD1[getD1(i,j)] = false;
fbD2[getD2(i,j)] = false;
}

return;
}

for (int I=i; I < N; ++I){
if (fbI) continue;

for (int J=0; J Q >> R;
if (!cin) return false;

N = Q+R;
res = 0;
pts = vector(N, vector(N));

for (int i=0; i pts[j];
}
}

vector A = vector(N, false), B = vector(N, false), C = vector(2*N-1, false), D = vector(2*N-1, false);

DFSQ(0,-1,0,R,Q,A,B,C,D);

cout

Подробнее здесь: https://stackoverflow.com/questions/796 ... nd-a-diffe