Enunțul problemei rover, de clasa a 10-a, dată în 2017 la ONI, se găsește pe PbInfo și InfoArena.

Rezumat rover

Avem un rover care se poate deplasa (cu o celulă în nord, sud, est sau vest) într-o matrice pătratică cu n linii și n coloane. Fiecare celulă (zonă) a matricei are o stabilitate reprezentată printr-un număr natural, iar rover-ul are greutatea g. O zonă cu stabilitatea mai mică decât g este considerată o zonă periculoasă pentru rover.

La prima cerință trebuie să determinăm numărul minim de zone periculoase pe care trebuie să le traverseze rover-ul pentru a ajunge de la zona (1, 1) la (n, n). La a doua cerință se cere greutatea maximă pe care o poate avea rover-ul pentru a putea ajunge din (1, 1) în (n, n) fără a traversa nicio zonă periculoasă.

Soluție rover – Cerința 1

Pentru prima cerință putem defini costul unei celule drept numărul minim de zone periculoase pe care rover-ul trebuie să le parcurgă pentru a ajunge la ea. Se observă ușor că atunci când trecem din celula A în celula B, avem relația de recurență cost(B) = cost(A) + zonăSigură(B). Evident, zonăSigură(B) este 1 dacă B este o zonă sigură, și 0 dacă nu. Această recurență ne indică faptul că putem aplica algoritmul lui Lee cu costuri. Adică, în loc să calculăm o distanță minimă, calculăm un cost minim, iar pentru a obține de fiecare dată un cost minim pentru celula curentă, ne vom expanda mai întâi din zonele sigure, iar abia apoi din cele periculoase.

Pentru a respecta această ordine a vizitării zonelor, putem folosi un deque în loc de coadă. În față adăugăm zone sigure, iar în spate zone periculoase. Asta ne garantează că întotdeauna zonele din deque vor fi ordonate descrescător în funcție de costul lor, și deci la fiecare pas continuăm cu cea mai sigură 🙂 Pentru a înțelege mai bine, puteți urmări mai jos cum arată deque-ul după fiecare dintre primii șase pași, pentru exemplul din enunțul problemei. Am folosit triplete de forma (a, b, c) cu semnificația „zona de coordonate (a, b), ce are costul c”.

Soluție rover – Cerința 2

Pentru a doua cerință putem folosi tehnica căutării binare pe rezultat. La fiecare pas testăm dacă mijlocul intervalului curent reprezintă o greutate pentru care se poate ajunge din zona (1, 1) în zona (n, n). Pentru verificare putem folosi atât algoritmul lui Lee, cât și un algoritm de fill. Eu am ales fill recursiv pentru că e mai scurt și oricum nu avem nevoie de lungimea drumului minim. Apoi, dacă greutatea este bună, continuăm căutarea binară în dreapta, în vederea găsirii unei greutăți mai mari. Dacă greutatea nu este bună, înseamnă că este prea mare, așa că vom căuta în stânga una mai mică.

Sursă C++ rover

Dacă ai vreo nedumerire cu privire la problema rover, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!