Soluție: drumeție

Problema este una clasică: avem o matrice și ne putem deplasa dintr-o celulă în alta în anumite condiții; dorim să alegem celula "optimă" dintre celulele în care putem ajunge.

În cazul de față putem porni din orice celulă a cărei valoare este 0 (enunțul garantează că astfel de celule există doar la margine). Le putem pune într-o coadă și le marcăm ca fiind deja vizitate. În continuare, atâta timp cât coada nu este vidă, extragem un element din ea și verificăm dacă putem introduce în coadă vreuna dintre celulele vecine. O astfel de celulă va fi introdusă dacă nu a fost deja vizitată și dacă altitudinea sa medie este cu cel mult K metri mai mare.

Pe măsură ce introducem elemente în coadă putem determina și maximul. Celulele introduse în coadă vor fi marcate ca fiind vizitate pentru a nu fi reintroduse în viitor. Soluția problemei va fi dată de maximul din momentul în care coada devine vidă.

Fiecare celulă va fi introdusă în coadă cel mult odată și în momentul extragerii sale sunt verificate cel mult patru alte celule (număr constant de operații). Așadar, ordinul de complexitate al algoritmului prezentat este O(MN), unde M și N sunt dimensiunile matricei.

Te-ar putea interesa și: