Eu am incercat sa rezolv cu un fel de back cu coada.
Pentru a obtine usor solutia la final, coada e structurata ca un arbore.
O mica problema ar fi ca un element din coada are 76 bytes (destul de mare), pentru ca in fiecare nod retin noua lista de nemuritori.
Cam asa arata structura:
struct QueueItem
{
Point From, To;
int RemainingNoobs;
int Parent;
Point Noobs[15];
};
Iau doar 50 puncte din pacate.
Am facut rost de testul 2 de la OJI, care e unul care imi pica si cu 500MB de memorie alocati tot iese din coada.
Algoritmul meu este sa sortez vectorul Noobs la fiecare element din coada, in functie de distanta la fiecare din punctele pe care le contine.
Pentru elementele cu distanta 1 calculez directia, si vad daca pot sa sar peste. Daca e ocupata celula, inseamna ca exista un element cu distanta 4 pe directia respectiva.
Cand gasesc o pozitie unde pot sari, adaug in coada structura ce contine toate detaliile necesare.
Nu am avut nici un TLE, deci ma gandesc ca algoritmul e ok.
Aici este toata sursa.