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

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


Timp maxim de execuţie/test:
0.3 secunde
Memorie totală disponibilă/stivă:
64MB/8 MB

Considerăm o matrice de numere naturale cu N linii şi N coloane. Definim un drum în această matrice ca fiind o succesiune maximală de componente alăturate pe linii şi coloane din matrice cu proprietatea că valorile din aceste componente sunt în ordine strict crescătoare. Succesiunea maximală se referă la faptul că drumul nu poate fi extins la unul din capetele sale. Considerăm ca exemplu matricea:

1  4  7
5  3  9
8 12  2

Un drum este 1 5 8 12. Alte drumuri sunt 3 9, sau 3 12, sau 1 4 7 9, sau 3 4 7 9. De menţionat că 3 5 8 nu este drum pentru că nu este maximal, el putând fi extins la unul din capete cu 12, obţinându-se drumul 3 5 8 12.

Cerinţă

Scrieţi un program care să determine numărul drumurilor din matrice.

Date de intrare

Fişierul de intrare drumuri1.in conţine pe prima linie un număr natural N reprezentând dimensiunile matricei. Pe următoarele N linii sunt descrise liniile matricei, pe fiecare linie aflându-se câte N numere naturale separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire drumuri1.out va conţine un singur număr natural reprezentând numărul de drumuri din matrice.

Restricţii

  • 3 <= n <= 300
  • Valorile memorate în matrice sunt numere cuprinse între 1 şi 10 000

Exemplu

drumuri1.in drumuri1.out Explicaţii
3
1 4 7
5 3 9
8 12 2
8 Cele 8 drumuri sunt:
1 4 7 9
1 5 8 12
3 4 7 9
3 5 8 12
3 9
3 12
2 9
2 12
prof. Dan Pracsiu
Grupul Şcolar "Ştefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la XOR 2011: triunghi3, cmmdcsecv, fillmat, secvb, siruri3
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
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, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, ny, oldest, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
surse trimise | ajutor