Nava stelară USS Enterprise a fost singura care a supraviețuit confruntării cu borgii din sectorul 001 (Terra). Din fericire, uriașa nava a borgilor a fost distrusă, așadar cel mai important sector al spațiului controlat de Federația Planetelor Unite nu a fost ocupat de borgi.
    Totuși, Enterprise este grav avariată și trebuie sa ajungă la șantierul naval din apropierea Lunii. Bătălia finală a avut loc în apropierea planetei Uranus, deci Cpt. Jean Luc Picard și restul echipajului care a supraviețuit luptei, trebuie să conducă nava prin centura de asteroizi aflată între Marte și Jupiter.
    Din nefericire, manevrabilitatea navei este redusă, iar o schimbare de direcție este foarte dificil de realizat. Din acest motiv Cpt. Jean Luc Picard îi cere Lt. Cmdr. Data să stabilească un curs de zbor prin această centură de asteroizi, astfel încât să fie necesare cât mai puține schimbări de direcție.
    Centura de asteroizi poate fi privită ca fiind o matrice ale cărei elemente pot avea fie valoarea 0 (corespunzătoare unei zone libere), fie valoarea 1 (corespunzătoare unei zone în care se află un asteroid).
    Navigatorul, Slt. Wesley Crusher, poate intra în centura de asteroizi prin orice punct dorește (va ajunge pe prima linie a matricei având direcția pe care o dorește; așadar, nu va fi efectuat nici un viraj pentru intrarea în centură). El trebuie să ajungă pe ultima linie a matricei, iar pentru a ieși din centură nu este necesară efectuarea unui viraj suplimentar.
    USS Enterprise se poate deplasa prin centura de asteroizi pe verticală, orizontală sau diagonală. Oricare tip de viraj este la fel de dificil de efectuat; pot fi realizate viraje de 45°, 90° sau 135°, înspre stânga sau înspre dreapta. Nava stelară nu va putea trece prin zonele în care se află asteroizi.
    După ce Lt. Cmdr. Data stabilește cursul de zbor, Lt. Cmdr. William Riker îl întreabă care este numărul virajelor care vor trebui efectuate.
    La această întrebare va trebui să răspundeți și voi, cunoscând configurația centurii de asteroizi.


Fișierul de intrare ASTEROID.IN conține pe prima linie două numere naturale M și N separate printr-un spațiu care reprezintă dimensiunile centurii de asteroizi.
    Pe fiecare dintre următoarele M linii se află un șir de N numere care pot fi 0 sau 1 și care nu sunt separate prin spații.

Fișierul de ieșire ASTEROID.OUT trebuie să conțină un singur număr natural V care reprezintă numărul minim al virajelor care trebuie efectuate.

  • 5 <= N, M <= 200.
  • elementele de pe prima coloană și de pe ultima coloană ale matricei care reprezintă centura de asteroizi vor avea întotdeauna valoarea 1


  • ASTEROID.IN
    8 10
    1101111011
    1100001101
    1100101111
    1001100101
    1110111001
    1010110001
    1001111001
    1101110011

    ASTEROID.OUT
    3

    În continuare este reprezentat traseul navei; pozițiile prin care trece nava sunt marcate cu '*'. Caracterele roșii indică poziții în care se efectuzează viraje.

    11*1111011
    110**01101
    11001*1111
    100110*101
    1110111*01
    1010110*01
    1001111*01
    1101110*11