Problem osmiu hetmanow

Question

Witam, mialem do napisania taki programik, ktory obsluguje problem n-hetmanow. Sek w tym, ze na szkopule dzialaja mi wszystkie oprocz jednego testu, ze wzgledu na czas. Pomozecie?

Tutaj tresc: https://tinyurl.com/4xva5d9w

A tutaj kodzik:

#include <iostream>
#include <cmath>

using namespace std;

struct Pole {
	int x, y;
};

Pole het[15];
int n, ile = 0;

// ile_akt - ile aktualnie hetmanow znajduje
// sie na szachownicy w aktualnej rekurencji
void symuluj(int ile_akt) {
	for (int i = 0; i < n; i ++) {
		bool ok = 1;
		// ok - czy da sie dostawic hetmana na konkretnym polu,
		// tzn. polu o wspolrzednych: {i, ile_akt}
		for (int j = 0; j < ile_akt; j ++) {
			// sprawdzam, czy hetmany sa w tej samej kolumnie
			if (het[j].x == i)
				ok = 0;
			// i na przekatnej
			else if (abs(het[j].x - i) == abs(het[j].y - ile_akt))
				ok = 0;
		}

		// jezeli ustawilem juz na szachownicy n hetmanow
		if (ok == 1 and ile_akt == n - 1) {
			// zwiekszam ilosc mozliwosci
			ile ++;
			// i wychodze z aktualnej rekurencji
			return;
		}
		else if (ok == 1) {
			het[ile_akt] = {i, ile_akt};
			symuluj(ile_akt + 1);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	symuluj(0);

	cout << ile;
}

 

Comments

Korzystasz z backtrackingu?

---

@polandonion, Wygląda dobrze, zwięźle i jasno. Zmień tylko inta na long longa bo może być tego 15^15 minus złę kombinacje

---

pasjonat_algorytmiki, chyba nie

---

@jankustosz1, dodalem long longa i te same rezultaty

---

@polandonion, Korzystasz z backtrackingu, tylko nie wiesz że to się tak nazywa :)

 

Nie wiem gdzie jest błąd, kod wygląda dobrze

Answer 1

Jeden Ci nie działa ze względu na czas z prostego powodu, jak odpalisz sobie swój program dla N = 14, to będzie się robił pewnie około 20s a max limit czasu na zadanie to 10s.

Comments

a wiesz moze jak to przyspieszyc?