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

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


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

Soricelul duce in continuare razboiul cu dusmanul traditional - pisica. Terenul de lupta este tot 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, locuri in care pisica nu-l poate ataca, de asemenea sunt marcate obstacolele, locuri pe unde nu poate trece nici pisica, nici soarecele. Se cunoaste pozitia soricelului, undeva in curte in afara adaposturilor si pozitia pisicii. Pisica alearga de doua ori mai repede dacat soricelul, ceea ce inseamna ca in timp ce soricelul face un pas, pisica poate face unul sau doi pasi, un pas reprezentand deplasarea de la un patrat de pe harta la unul invecinat pe orizontala, verticala sau diagonala. Avand in minte harta curtii soricelul incearca sa afle spre ce adapost sa se indrepte astfel incat sa fie sigur ca pisica nu-l ajunge, indiferent de strategia ei de urmarire. 

Cerinta

Scrieti un program care sa determine toate adaposturile la care soricelul poate ajunge inaintea pisicii.

Date de intrare

Pe prima linie a fisierului de intrare soricel2.in sunt scrise doua numere reprezentand dimensiunile hartii. Pe urmatoarea linie este data pozitia soricelului. Pe linia a treia este pozitia pisicii. Pe linia a patra este numarul de adaposturi. Pe liniile urmatoare sunt pozitiile adaposturilor. Urmeaza o linie cu numarul de obstacole. Pe liniile urmatoare sunt pozitiile obstacolelor. Toate pozitiile sunt perechi de numere naturale reprezentand linia si coloana corespunzatoare. Numerotarea liniilor si coloanelor incepe de la 1. Numerele de pe aceeasi linie sunt separate de cate un spatiu.

Date de iesire

Prima linie a fisierului soricel2.out va contine numarul adaposturilor la care soricelul poate ajunge in siguranta. Pe liniile urmatoare sunt date coordonatele adaposturilor in acelasi format ca la fisierul de intrare. Adaposturile sunt scrise in ordinea crescatoare a liniei pe care se gasesc, iar adaposturile de pe aceeasi linie in ordinea crescatoare a coloanei. Daca nu exista nici un adapost in care sa intre soricelul inainte de a fi ajuns de pisica, in fisierul de iesire se va scrie doar numarul 0. 

Restrictii

Dimensiunile dreptunghiului nu depasesc 100 x 100. Exista cel mult 500 de adaposturi si 500 de obstacole. Pe pozitia initiala a soarecelui si a pisicii nu sunt adaposturi sau obstacole. De asemenea pozitia nici unui adapost nu coincide cu pozitia unui obstacol. Daca soricelul ajunge la patratul corespunzator unui adapost simultan cu pisica el este mancat inainte de a intra in adapost.

Exemplu

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

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, soricel1, traseu, zapezi, banda10, 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, soricel1, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, tort1, triunghi4, bile6, zmax
Despre coada: balanta, inginer, camp, rebus, harta, insule, volei, lbd, magic3, axa, cadere, reinvent, ocean14, iepuras2, sah, balls, cd, toys, radio, caini, subperm, castel, excursia, casute, masina2, salvare, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, ny, oldest, drumuri1, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
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, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, 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, 2ndesc, 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
Despre Lee: inginer, insule, lbd, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, masina2, paianjen, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ny, ai, robot3, pixy, valet, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3, wow, panda
surse trimise | ajutor