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

ultima problemă
grupă: medie
sursă: ONI 2004
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
paianjen


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Un păianjen a ţesut o plasă, în care nodurile sunt dispuse sub forma unui caroiaj cu m linii (numerotate de la 0 la m-1) şi n coloane (numerotate de la 0 la n-1) ca în figură.



Iniţial, oricare două noduri vecine (pe orizontală sau verticală) erau unite prin segmente de plasă de lungime 1. În timp unele porţiuni ale plasei s-au deteriorat, devenind nesigure. Pe plasă, la un moment dat, se găsesc păianjenul şi o muscă, în noduri de coordonate cunoscute.

Cerinţă

Să se determine lungimea celui mai scurt traseu pe care trebuie să-l parcurgă păianjenul, folosind doar porţiunile sigure ale plasei, pentru a ajunge la muscă. De asemenea, se cere un astfel de traseu.

Date de intrare

Fişierul de intrare paianjen.in conţine:
– pe prima linie două numere naturale m n, separate printr-un spaţiu, reprezentând numărul de linii şi respectiv numărul de coloane ale plasei;
– pe a doua linie două numere naturale lp cp, separate printr-un spaţiu, reprezentând linia şi respectiv coloana nodului în care se află iniţial păianjenul;
– pe linia a treia două numere naturale lm cm separate printr-un spaţiu, reprezentând linia şi respectiv coloana pe care se află iniţial musca;
– pe linia a patra, un număr natural k, reprezentând numărul de porţiuni de plasă deteriorate;
– pe fiecare dintre următoarele k linii, câte patru valori naturale l1 c1 l2 c2, separate prin câte un spaţiu, reprezentând coordonatele capetelor celor k porţiuni de plasă deteriorate (linia şi apoi coloana pentru fiecare capăt).

Date de ieşire

Fişierul de ieşire paianjen.out va conţine pe prima linie un număr natural min reprezentând lungimea drumului minim parcurs de păianjen, exprimat în număr de segmente de lungime 1. Pe următoarele min+1 linii sunt scrise nodurile prin care trece păianjenul, câte un nod pe o linie. Pentru fiecare nod sunt scrise linia şi coloana pe care se află, separate printr-un spaţiu.

Restricţii

1 <= m, n <= 140
1 <= k <= 2*(m*n-m-n+1)

Lungimea drumului minim este cel mult 15000.
Pentru datele de test există întotdeauna soluţie. Dacă problema are mai multe soluţii, se va afişa una singură.
Porţiunile nesigure sunt specificate în fişierul de intrare într-o ordine oarecare. Oricare două porţiuni nesigure orizontale se pot intersecta cel mult într-un capăt. De asemenea, oricare două porţiuni nesigure verticale se pot intersecta cel mult într-un capăt.
Se acordă 30% din punctaj pentru determinarea lungimii drumului minim şi 100% pentru rezolvarea ambelor cerinţe.

Exemple

paianjen.inpaianjen.outExplicaţii
9 7 2 3 7 4 8 2 4 2 5 2 3 3 3 3 0 3 1 3 3 3 5 4 4 5 4 6 4 6 5 6 5 7 5 7 2 7 3 8 2 3 2 2 3 2 4 2 5 2 6 2 6 3 7 3 7 4 Problema corespunde figurii de mai sus. Traseul optim este desenat cu linie groasă, iar porţiunile nesigure sunt desenate punctat.

autor: Prof. Carmen Popescu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, bifo, joc9, pal, romeo, seceta, antena, avere, joc11, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
De acelaşi autor: light, sort, iepuras, pahare, turist, arthur, pento, cod2, game, ambigram, jokes, trecere, zumzi, cifru3, pamant, pixy, triburi, culori1, cifre5
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, soricel2, masina2, salvare, 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
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, medii, monkey, scara1, numere8, banda1, spirala1, cofetar, gradina, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu
Despre recursivitate: tren, mere, chimie, sarpe, soldati, formule, infinit, compress, ploaia, cartoane, sub, metro, windows, lacuri, apel, maxq, pav, joc11, suma2, monkey, csir, lsort, imagine, dir, desert, echitabil, rez, logic, gradina, links, dreptunghiuri, expresie1, cumpanit, reziston
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, soricel1, antena, avere, 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
Despre Lee: inginer, insule, lbd, ocean14, iepuras2, sah, radio, lacuri, castel, excursia, soricel2, masina2, suma2, soricel3, cub2, alee, rj, taxe1, sotron1, tom, ny, ai, robot3, pixy, valet, oras1, maxtri, lgdrum, gheizere, abq, cartite, joc21, traseu3
surse trimise | ajutor