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

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


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

Soricelul duce un razboi continuu cu dusmanul traditional. Terenul de lupta este curtea, reprezentata pe harta soricelului de un dreptunghi de dimensiuni intregi, impartit, pentru o mai usoara orientare, in patrate de dimensiune 1. Pe harta sunt marcate pozitiile (patratele) unde se gasesc adaposturile soricelului si pozitiile unde se gasesc rezervele sale de hrana. Soricelul, care se gaseste intr-un adapost, vrea sa se furiseze pana la un depozit de hrana de unde sa-si ia portia de mancare si sa fuga repede intr-un alt adapost.Cat mai repede inseamna cu cat mai putini pasi, un pas reprezentand deplasarea de la un patrat de pe harta la unul invecinat pe orizontala, verticala sau diagonal. 

Cerinta

Cunoscand configuratia hartii si pozitia initiala a soricelului determinati depozitul de hrana si adapostul in care revine acesta astfel ca numarul total de pasi facuti sa fie minim 

Date de intrare

Pe prima linie a fisierului de intrare soricel1.in sunt scrise doua numere reprezentand dimensiunile hartii. Pe a doua linie este scris numarul de adaposturi, iar pe urmatoarele linii pozitia acestora. In continuare, pe o linie noua se gaseste numarul de depozite de hrana urmat de linii pe care se gasesc coordonatele acestor depozite. In fine, pe ultima linie se gaseste numarul de ordine al adapostului in care se afla soricelul. Numerele de pe aceeasi linie sunt separate de un spatiu. Coordonatele care precizeaza pozitia unui adapost sau depozit de hrana sunt doua numere naturale - linia si coloana patratului respectiv. Numerotarea liniilor si a coloanelor incepe de la 1. Numerele de ordine ale adaposturilor, respectiv depozitelor, incep de la 1 si respecta ordinea in care au fost scrise in fisierul de intrare.

Date de iesire

In fisierul soricel1.out se va scrie pe prima linie numarul de ordine al depozitului de hrana ales iar pe a doua linie numarul de ordine al adapostului in care se va retrage soricelul.  Daca sunt mai multe solutii posibile se va scrie cea care are numarul de ordine al depozitului de hrana cat mai mic, iar daca sunt doua solutii cu acelasi depozit se va scrie cea in care numarului adapostului este cat mai mic.

Restrictii

Dimensiunile hartii sunt cel mult 200 x 200, exista cel mult 500 de adaposturi si cel mult 500 de depozite de hrana. Nici un depozit de hrana nu coincide cu un adapost. 

Exemplu

soricel1.in soricel1.out
5 6
3
1 3
4 4
2 6
2
3 6
5 2
1

3

prof. Nistor Mot
Colegiul National "N. Balcescu"- Braila

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, zoo, secvente
De acelaşi autor: cursa, insule, termen, div, mese, hperm, zmeu, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, parc, circular, sant, mobile, pattern, mutare, concurs2, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, tort1, triunghi4, bile6, zmax
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor