.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » parc

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
parc


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
15 MB/1 MB

In fiecare zi Gigel vine de la scoala acasa trecand prin parc. Parcul este un teren de forma patrata care are un obstacol (o groapa) pe care Gigel trebuie sa o ocoleasca. Dupa multe drumuri Gigel nu a reusit inca sa-si dea seama care e cel mai scurt drum spre casa; trebuie sa ocoleasca groapa prin stanga sau prin dreapta? Pentru a-l ajuta sa afle raspunsul la intrebare Gigel va pune la dispozitie o harta a parcului sub forma unei matrice patrata cu valori 0 si 1, 0 reprezentand terenul accesibil, 1 obstacolul. Scoala este in coltul stanga-sus al matricei iar casa in coltul din dreapta jos. Cele 4 margini ale terenului sunt accesibile. Pentru a trece dintr-o celula a matricei intr-o celula invecinata pe orizontala, verticala sau diagonala Gigel face un pas. El nu face salturi, deci nu poate trece dintr-o celula decat intr-una din cele maximum 8 celule invecinate.

Cerinta

Scrieti un program care calculeaza numarul minim de pasi necesari pentru a ajunge de la scoala acasa mergand prin stanga obstacolului, apoi mergand prin dreapta obstacolului.

Date de intrare

Pe prima linie a fisierului de intrare parc.in se gaseste dimensiunea matricei. Pe urmatoarele linii e descrisa matricea ca un sir de 0 sau 1 cu cate un spatiu intre numerele de pe aceeasi linie.

Date de iesire

Prima linie a fisierului parc.out va contine doua numere separate de un spatiu. Primul numar reprezinta numarul minim de pasi prin care se poate ajunge de la scoala acasa mergand prin stanga obstacolului, al doilea numar - numarul minim de pasi necesari mergand prin dreapta obstacolului. Stanga si dreapta se considera in raport cu directia de mers.

Restrictii

  • 3 <= dimensiunea matricei <= 250

Exemplu

parc.in parc.out
5
0 0 0 0 0
0 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
5 7

prof. Nistor Mot
Colegiul National "N. Balcescu" - Braila
Contact:emotz_ro@yahoo.co.uk

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2003: newcomp, rima, algebra, turn1, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, stop, hanoi, lift, pic, sms, fibo, bac, circular, logn, lex, joc7, cuburi1, sant, mobile, pattern, oras, produs, mutare, viteza, concurs2, furnici, homeless, subsir
De acelaşi autor: cursa, insule, termen, div, mese, hperm, zmeu, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, circular, sant, mobile, pattern, mutare, concurs2, soricel1, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, tort1, triunghi4, bile6, zmax
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor