h3. Boom

Vom construi un graf din cele $2^N^$ stari posibile. Prin stare intelegem un numar binar in care bitii de $1$ reprezinta locurile in care s-ar putea afla sobolanul. Pentru fiecare astfel de nod, exista $M$ muchii la alte noduri, care se obtin aplicand bomba asupra pozitiilor si avansarea pozitiilor ramase. Deoarece muchiile au costuri numere naturale, iar graful nu este neaparat aciclic vom aplica algoritmul Dijkstra, pentru a determina drumul de cost minim de la nodul $2^N^-1$ la nodul {$0$}. Pentru a se incadra in timp era necesara implementarea cozii de prioritate cu heap-uri. Complexitate finala {$O(2^N^ * N * M)$}.

Vom construi un graf din cele $2^N^$ stari posibile. Prin stare intelegem un numar binar in care bitii de $1$ reprezinta locurile in care s-ar putea afla sobolanul. Pentru fiecare astfel de nod, exista $M$ muchii la alte noduri, care se obtin aplicand bomba asupra pozitiilor si avansarea pozitiilor ramase. Deoarece muchiile au costuri numere naturale, iar graful nu este neaparat aciclic vom aplica algoritmul Dijkstra, pentru a determina drumul de cost minim de la nodul $2^N-1^$ la nodul {$0$}. Pentru a se incadra in timp era necesara implementarea cozii de prioritate cu heap-uri. Complexitate finala {$O(2^N^ * N * M)$}.

h3. PetSoft